text: # 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
metadata: {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}