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.000 mine2      10.000                  10.000 mine3      20.000      10.000 ----     42 VARIABLE x.L  move i to j: assignment             mine2 mine1       1.000 mine2       1.000 mine3       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.