Determine the optimal number and location of the plants and pipelines in the 7 cities.

Question

There are 7 cities, up to 4 plants to be made in them and up to 18 pipelines to be made connecting them.

Determine the optimal amount of plants and pipelines to be made, the optimal locations of the plants and pipelines (if any) and the optimal capacities of the plants (if any).

---

---

What I tried:

---

Variables:

Let $y_i$ be the number of plants to be constructed in city $i$.

So, $y_i = 0-4$ and $i=1-7$

Let $x_i = 1$ if no plants are constructed in city $i$ and $0$ otherwise.

Let $pc_{i1,i2}$ be the cost of constructing a pipeline from city $i1$ to city $i2$.

Let $z_{i1,i2} = 1$ if a pipeline is to be constructed from city $i1$ to city $i2$ and $0$ otherwise.

So, $z_{i,i} = 0$.

Let $pcap_{i1,i2}$ be the capacity of a pipeline that would be constructed.

Let $d_i$ be approximate discharge in city $i$. It is 5 times the population.

Let $plant_{i}$ be the combined capacities for plants that would be in city i.

---

Objective function:

Min

$$z = [1m, ..., 1.4m] \cdot [y_1, ..., y_7] + \sum_{i1}\sum_{i2} pc_{i1,i2}z_{i1,i2}$$

---

Constraints:

1. Since we want at most 4 plants,

$$\sum_{i=1}^{7} y_i \le 4$$

2. I think the combined capacities of plants in city $i$ should be greater than or equal to

approximate discharge of wastewater in that city

plus the combined capacities of the pipelines that transfer wastewater from other cities to city $i$

minus the combined capacities of the pipelines that transfer wastewater to other cities from city $i$

$$d_i + \sum_{i1=1}^{7} pcap_{i1,i} z_{i1,i} - \sum_{i1=1}^{7} pcap_{i,i1} z_{i,i1} \le plant_{i} + M(x_i)$$

3. I think cities without plants should end up with zero wastewater. Otherwise, we wouldn't need to construct any plants............I guess?

$$d_i + \sum_{i1=1}^{7} pcap_{i1,i} z_{i1,i} - \sum_{i1=1}^{7} pcap_{i,i1} z_{i,i1} = 0 + M(1-x_i)$$

4. The capacity of a pipeline from city $i1$ to $i$ should be greater than or equal to the discharge from city $i1$

$$pcap_{i1,i} \ge d_{i1}$$

---

Is that right?

Strange things:

1. I computed the combined approximate discharge of wastewater in all cities:

It turns out to be 2.25m, meanwhile the combined maximum capacities of all plants is merely 400,000. How can only 4 plants handle 2.25m of wastewater if their maximum capacity is 400,000

2. Since the cost of constructing a plant doesn't seem to vary depending on its capacity, why not have $plant_{i} = 100,000y_i$?

---

From Chapter 3 here.

Answer 1

Let $y_i$ be a binary that equals $1$ if and only if a plant is constructed on site $i$, and let $x_{ij}$ be another binary that equals $1$ if and only if cities $i$ and $j$ are linked by pipeline (from $i$ to $j$).

$$ \mbox{Minimize } Z= \sum_{i=1}^7c_iy_i + \sum_{i=1}^7\sum_{j\;|\; \exists \;link(i,j)}10\frac{500}{100}p_ic_{ij}x_{ij} $$

subject to $$ \sum_{i=1}^7y_i\le 4\\ \sum_{i=1}^7\sum_{j=1}^7x_{ij}\le18\\ 10\frac{500}{100}p_iy_i+\sum_{j\;|\; \exists \;link(j,i)}10\frac{500}{100}p_jx_{ji}\le 100 000 +M(1-y_i)\quad \forall i=1,\cdots,7\\ 1-y_i\le \sum_{j\;|\; \exists \;link(i,j)} x_{ij}\quad \forall i=1,\cdots,7\\ x_{ij},y_i \in \{0,1\} \quad \forall i,j=1,\cdots,7 $$

Further detail

The first constraints limit the number of plants to 4.

The second constraints limit the number of pipelines to 18.

The third constraints are capacity constraints. You need to consider the wastewater coming from a city where a plant is built, and add the wastewater coming from neighboring cities connected to this city.

The fourth constraints impose a link between city $i$ and a city $j$ if there is no plant built in city $i$.