How can I linearize the distance from two points?

Question

I'm studying Operations Resarch and the professor give us the following problem:

• There is a 10*10 matrix in which there are 20 villages on random coordinates.
• We have to drop two supply packages (let's say a and b).
• Once a packages are dropped, each village is assigned to the closest package.

The objective is to find Xa,Ya and Xb,Yb in order to minimize the sum of these distances.

The problem is that the model has to be linear (Linear Programming) and with less than 300 variables. I think I found a model but I've used the non-linear distance function.

There's a way to linearize it?
Thanks.

Edit: my current model is:

$ X_1 $= row of the first package
$ Y_1 $= column of the first package

$ X_2 $= row of the second package
$ Y_2 $= column of the secondo package

$ X_vi $= row of the i-village
$ Y_vi $= column of the i-village
forall i from 1 to 20.

define $d_xi$ as the distance of the i-village from the x-package $$ d_1i = sqrt[2]((X_1 - X_vi)^2 + (Y_1 - Y_vi)^2) $$ $$ d_2i = sqrt[2]((X_2 - X_vi)^2 + (Y_2 - Y_vi)^2) $$

logic variables:
$ L_1i $= 1 iif d_1i less than d_2i, 0 otherwise
$ L_2i $= 1 iif d_2i less than d_1i, 0 otherwise

objective function:
minimize: $ \sum_{i=0}^{20} ((d_1i * L_1i) + (d_2i * L_2i)) $

constraints:
$ L_1i + L_2i = 1 \tag 1$
$ (d_2i - d_1i) * L_1i >= 0 \tag 2$
$ (d_1i - d_2i) * L_2i <= 0 \tag 3$
• all the coordinates are contained in {1,2,...,10}

i think this is less-equal-than 300 variables

Answer 1

Here's a mixed integer linear programming formulation with 220 variables and $1+20\binom{100}{2}$ linear constraints. Let $V=\{1,\dots,20\}$ denote the set of villages. Let parameter $d_{i,j}^v$ denote the distance from village $v$ to location $(i,j)$. Let $$P=\{(i_1,j_1,i_2,j_2)\in\{1,\dots,100\}^4:i_1 < i_2 \lor ((i_1 = i_2) \land (j_1 < j_2))\}$$ be the set of pairs of distinct locations. Let binary decision variable $y_{i,j}$ indicate whether a package is dropped at $(i,j)$, as in @Kuifje's answer. Let decision variable $z_v$ be the distance from village $v$ to the closest package. The problem is to minimize $\sum_v z_v$ subject to: \begin{align} \sum_{i,j} y_{i,j} &= 2\\ z_v &\ge \min\left(d_{i_1,j_1}^v,d_{i_2,j_2}^v\right)(y_{i_1,j_1}+y_{i_2,j_2}-1)&&\text{for all $v\in V, (i_1,j_1,i_2,j_2)\in P$}\\ y_{i,j} &\in\{0,1\}&&\text{for all $i,j$} \end{align} The idea is that $y_{i_1,j_1} = y_{i_2,j_2} = 1$ forces $z_v \ge \min\left(d_{i_1,j_1}^v,d_{i_2,j_2}^v\right)$.

Answer 2

I would say please give more details on your non linear function.

In general if you function can be expressed as a sum of something linear and something that is non-linear and this non-linear part isn't a dominant part that you can just omit\truncate this non linear part, as long as it remains a distance function. $$d(x,y)=L(x)+NL(x)\quad\text{become}\quad \tilde d(x,y)=L(x)$$

I would call $\tilde d$ an approximation of $d$. However, the distortion created by this linearization may change the final result, which hopefully remains in a range acceptable error, i.e. $$\|d(x,y)-\tilde d(x,y)\|<\epsilon,$$ otherwise I guess you cannot use this trick.

Answer 3

How about this? Define the following boolean variables:

• $y_{ij}=1$ if and only if a package is dropped at location $(i,j), i,j=1,…,10;$
• $x_{ij}^v=1$ if and only if village $v$ is assigned to location $(i,j), i,j=1,…,10,$ $v=1,…,20$.

Objective function: Minimize $$\sum_{i=1}^{10}\sum_{j=1}^{10}\sum_{v=1}^{20}d_{ij}^vx_{ij}^v$$

where $d_{ij}^v$ is the distance (known with the matrix) between village $v$ and location $(i,j)$, and add the following constraints:

• drop exactly 2 packages: $$\sum_{i=1}^{10}\sum_{j=1}^{10}y_{ij}=2$$
• assign each village to one of the packages: $$\sum_{i=1}^{10}\sum_{j=1}^{10}x_{ij}^v=1\quad \forall v=1,…,20$$
• a village can only be assigned to a location where there is a package: $$x_{ij}^v\le y_{ij}\quad \forall v=1,…,20,\quad \forall i,j=1,…,10$$

The model is linear, but it has more than 300 variables (it has 2100!). Maybe I misunderstood the problem. Maybe there is a way to get rid of some variables.