3
$\begingroup$

I want to use Excel solver to solve the following integer linear program:

A company wants to select $p$ locations among a set of $m$ possible sites for constructing polluting plants in a contemporary world. The $m$ candidate sites are located on a territory containing different cities. We have:

  • $d_{ij}$ the distance between city $i$ and site $j$
  • $P_i$ the population (in thousand of inhabitants) of city $i$

I imagined experts that thought that a city was threatened if there was a polluting plant located less than 2 km from it.

The authorities' point of view wants to minimize nuisance. They want to minimize the number of inhabitants threatened by the $p$ selected plants.

  • At most 5% of the population of $n$ cities are threatened (constraint imposed by the authorities).
  • The demand of a city is delivered by a single plant
  • The company minimizes its total transportation cost

My attempt

$$\begin{cases} \min & \sum_i b_{i}p_i\\ %&s_{i}=b_i\times P_i\mbox{ number of people of city $i$ endangered by site $j$}\\ &b_i\le b_j\\ &\sum_{j=1}^mb_j=p\\ &2- d_{ij} \le M. b_{i} \\ %\mbox{ constraint over the distance to flag an endangered population}\\ %&\sum_i b_i= \mbox{ number of sites we want}\\ &b_i,b_j \in \{0,1\},\forall i \in \mathbb{N}^* \end{cases}$$

With the additional variables :

  • $b_i$ a boolean variable telling me if city $i$ is threatened.

  • $b_j$ a boolean variable telling me if location $j$ is used to settle a plant.

  • $M$ is a very large number

We want to minimize the sum of $\sum b_i p_i$, the number of people endangered. I thought about creating a variable $b_i$, standing for "take into account population $i$" with the following test :

$$2- d_{ij} \le M. b_i$$

$$\begin{cases} b_i = 0 \mbox{ if we don't have to take the population of city $i$ into account}\\ b_i = 1 \mbox{ otherwise} \end{cases}$$

But I think it is too much variables. I don't think that $b_j$ is necesary because if a site wasn't used to settle a plant we won't have the distances. Would the following program be better ?

$$\begin{cases} \min & \sum_i b_{i}p_i\\ %&s_{i}=b_i\times P_i\mbox{ number of people of city $i$ endangered by site $j$}\\ &2- d_{ij} \le M. b_{i} \\ %\mbox{ constraint over the distance to flag an endangered population}\\ %&\sum_i b_i= \mbox{ number of sites we want}\\ &b_i,b_j \in \{0,1\},\forall i \in \mathbb{N}^* \end{cases}$$

$\endgroup$
  • $\begingroup$ $b$ means two different things. The alphabet has 20+ letters. Use them. $\endgroup$ – Rodrigo de Azevedo Apr 27 '17 at 9:39
  • $\begingroup$ What do you mean by better? $\endgroup$ – Michiel uit het Broek Jun 27 '17 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.