Modellering a Integer Linear Program

Question

Warning; !! Long post !!

Note; This is not a homework assignment, but rather an old exam question I'm trying to figure out. If you read on, you'll notice that I've put quite some work in on it already. Questions are in the bottom of the post. Any help / input is welcome.

So I'm given the following assignment;

1. In a city of X there's 8 schools, and 1000 children.
2. Closing a school, for good, yields $p_{j}$ cash, where $j \in \left[1,\ldots,8\right]$.
3. A school cannot be closed, when children are attending it.
4. All 1000 children must attend school.
5. All schools have a maximum of 300 attendees.
6. No school can have a negative number of attendees.
7. Each child can attend at most one school.
8. Having child $i$ going to school $j$ has a cost of $c_{i,j}$.

The city's counsel wants to decide which schools to close, and which children should attend which schools, while minimize the city's expenses to school services.

And I've model the issue as stated below;

I've:

• Create a binary matrix; $attend = Mat_{1000 \times 8}\left(\left\{0,1\right\}\right)$ to represent if a given child goes to a given school ($attend_{i,j}$).

• Setup a list of constraints matching the above rules;

  1. No constraints
  2. No constraints
  3. "constraint" in object function
  4. $\sum_{i=1}^{1000} \sum_{j=1}^{8} attend_{i,j} = 1000$
  5. \begin{align*} \sum_{i=1}^{1000} attend_{i,1} &\leq 300 \\ \sum_{i=1}^{1000} attend_{i,2} &\leq 300 \\ \vdots \\ \sum_{i=1}^{1000} attend_{i,7} &\leq 300 \\ \sum_{i=1}^{1000} attend_{i,8} &\leq 300 \\ \end{align*}
  6. \begin{align*} \sum_{i=1}^{1000} attend_{i,1} &\geq 0 \\ \sum_{i=1}^{1000} attend_{i,2} &\geq 0 \\ \vdots \\ \sum_{i=1}^{1000} attend_{i,7} &\geq 0 \\ \sum_{i=1}^{1000} attend_{i,8} &\geq 0 \\ \end{align*} 7. \begin{align*} \sum_{j=1}^{8} attend_{1,j} &= 1 \\ \sum_{j=1}^{8} attend_{2,j} &= 1 \\ \vdots \\ \sum_{j=1}^{8} attend_{999,j} &= 1 \\ \sum_{j=1}^{8} attend_{1000,j} &= 1 \\ \end{align*}

• Defined a helper function; $attendees\left(j\right) = \sum_{i=0}^{1000} attend_{i,j}$

• Defined the school closing as: $Savings\left(j\right) = \left(\left(\left|\frac{attendees\left(j\right)}{attendees\left(j\right)}\right| \cdot \left(-1\right)\right) + 1 \right) * p_{j}$

Such that it returns $0$, if there's any children going to that specific school and $p_{j}$ otherwise.

• Defined the total school closing as; $\sum_{j=0}^{8} Savings\left(j\right)$

• Defined the total cost of having children going to school as; $\sum_{i=0}^{1000} sum_{j=0}^{8} attend_{i,j} \cdot c_{i,j}$

And I've defined my object function as (based upon the two above); $\left(\sum_{i=0}^{1000} \sum_{j=0}^{8} attend_{i,j} \cdot c_{i,j}\right) - \left(\sum_{j=0}^{8} Savings\left(j\right)\right)$

However (and these are my questions);

1. I'm not sure whether I've done this correct.
2. I'm not sure how to check it.
3. I think that there should be a simpler way to solve this issue.

Answer 1

To simplify notation, let $$ x_{ij} = \begin{cases} 1 & \text{if child } i \text{ attends school } j \\ 0 & \text{otherwise.} \end{cases} $$ All of your constraints can be summarized as \begin{align*} x_{ij} & \in \{0,1\} \\ \sum_j x_{ij} & = 1 \quad \text{for all } i, \quad \text{(each child attends exactly one school)} \\ \sum_i x_{ij} & \leq 300 \quad \text{for all } j \quad \text{(max attendance constraint).} \end{align*} Now you need to define a new binary variable to decide whether a school is empty or not, i.e., $$ y_j = \begin{cases} 1 & \text{if } \sum_i x_{ij} = 0 \\ 0 & \text{otherwise.} \end{cases} $$ This can be done by adding the constraints \begin{align*} y_j & \in \{0,1\} \\ 1-y_j & \leq \sum_i x_{ij} \qquad \text{for all } j \\ 300 (1-y_j) & \geq \sum_i x_{ij} \qquad \text{for all } j. \end{align*} The first constraint forces $y_j=1$ when the sum is zero (the sum is always at least zero). When the sum is $> 0$, it is at least equal to 1 so the second constraint forces $1-y_j$ to be at least equal to $1/300$. Since $y_j$ is binary, this means $y_j = 0$.

Your objective function to be minimized becomes $$ \sum_i \sum_j x_{ij} c_{ij} - \sum_j y_j p_j. $$