## Tuesday, August 2, 2016

### Dynamic programming vs MIP

Many problems solved by dynamic programming can also be formulated as a Mixed Integer Programming problem. Here is a very simple problem. The participant is asked to provide a Dynamic Programming algorithm that solves this problem to optimality. A MIP approach would be even simpler. Given $$n$$ gold mines located along a river. Each mine has a location $$x_i$$ (measured along the river) and has $$w_i$$ tons of gold. The goal is to select a subset of of the mines as pick-up points. The number of pick-up points is given: $$k$$. The cost to move gold from mine $$i$$ to pick-up point $$j$$ is $$c_{i,j}=w_i |x_i-x_j|$$.

This actually looks very much like an assignment problem:

 \boxed{\begin{align} \min\>&\sum_{i,j} c_{i,j} x_{i,j}& \\ & \sum_j x_{i,j} = 1 &\forall i\\& \sum_i x_{i,j} = 1 &\forall j\\ & x_{i,j}\in \{0,1\} \end{align}}

We need to allow a destination $$j$$ to serve multiple sources $$i$$, so first we drop the second constraint. The second issue is that we need to count the number of destinations that are used. We can do this by introducing a binary variable $$y_j$$ with $$\sum_j y_j=k$$. If $$y_j=0$$ we need to ensure $$x_{i,j}=0$$. This can simply be modeled as $$x_{i,j}\le y_j$$. The complete model can now look like:

 \boxed{\begin{align} \min\>&\sum_{i,j} c_{i,j} x_{i,j} & \\ & \sum_j x_{i,j} = 1 & \forall i\\& x_{i,j}\le y_j & \forall i,j\\ &\sum_j y_j = k \\& x_{i,j},y_j \in \{0,1\} \end{align}}

The solution for the example looks like

 ----     42 PARAMETER c  cost of moving i to j             mine1       mine2       mine3 mine1                  10.000      20.000mine2      10.000                  10.000mine3      20.000      10.000 ----     42 VARIABLE x.L  move i to j: assignment             mine2 mine1       1.000mine2       1.000mine3       1.000 ----     42 VARIABLE y.L  mine is collection point mine2 1.000

Notes:

1. We don’t need to worry about what happens with the gold already at a pick-up point. The model will automatically select $$x_{j,j}=1$$ when $$j$$ is a pick-up point as that is very cheap (i.e. $$c_{j,j}=0$$).
2. We can aggregate the equation $$x_{i,j}\le y_j$$ into $$\sum_i x_{i,j} \le n \cdot y_j$$. Often the disaggregated version shows better performance although we add more equations.
3. Without using a proper Dynamic Programming algorithm or a MIP/CP model this is more difficult. Here is an example of someone on the wrong track. Many programmers are not aware of these technologies.