# How to linearize a not linear program with excel?

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}$$

• $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}$$

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