How can we express an integer linear program as a dynamic program? (Operations Research)

Question

We are given the following integer linear program:

\begin{equation} \begin{array}{c} \max x_{1}+2 x_{2}+2 x_{3}+3 x_{4} \\ \text { such that } 2 x_{1}+3 x_{2}+x_{3}+2 x_{4} \leq 4, \\ \text { where } x_{1}, x_{2}, x_{3}, x_{4} \in\{0,1\} \end{array} \end{equation}

The task is to express this as a dynamic program.

I know that we have to simplify a complicated problem by breaking it down into simpler sub-problems in a recursive manner. However, I cannot figure out how to do so in such a context, no recursive pattern comes to mind.

Help much appreciated.

Answer 1

Let $v_i$ be the objective coefficient of $x_i$, and let $w_i$ be the constraint coefficient of $x_i$. Let $f(k,b)$ be the maximum when you restrict to the variables $x_1,\dots,x_k$ and a budget of $b$, so that the original problem is to compute $f(4,4)$. By conditioning on the value of $x_k\in\{0,1\}$ we obtain DP recursion $$f(k,b) = \max\{f(k-1,b), v_k+f(k-1,b-w_k)\}$$

Answer 2

Let $f(x) = x_1 + 2x_2 + 2x_3 + 3x_4$ denote your objective with $x =(x_1, x_2, x_3, x_4) \in \{0,1\}^4$ and $g(x) = 2x_1 + 3x_2 + x_3 + 2x_4 - 4 \leq 0$ the constraint. As $f$ is increasing in all of its arguments, $x_i = 1$ if the constraint allows it. Assume there is a given history $(x_1, x_2, x_3)$ of decisions. Now we determine the optimal $x_4^*$ with respect to any history $(x_1,x_2,x_3) \in \{0,1\}^3$ and $g(x) \leq 0$ [some histories are not feasible (e.g. $(1,1,1)$) and will be basically overwritten by previous decisions (i.e. if $(x_1,x_2) = (1,1)$, then $x_3 = 0$ such that $(1,1,1)$ is a branche that will never be reached)] \begin{align} x_4^*(0, 0, 0) = 1\\ x_4^*(1, 0, 0) = 1\\ x_4^*(0, 1, 0) = 0\\ x_4^*(0, 0, 1) = 1\\ x_4^*(1, 1, 0) = 0\\ x_4^*(1, 0, 1) = 0\\ x_4^*(0, 1, 1) = 0\\ x_4^*(1, 1, 1) = 0 \end{align} Next we determine $x_3^*$ with respect to given $(x_1,x_2)$ and the constraint \begin{align} x_3^*(0,0) = 1\\ x_3^*(1,0) = 1\\ x_3^*(0,1) = 1\\ x_3^*(1,1) = 0 \end{align} Apparently $x_2^*(0) = 1$ and $x_2^*(1) = 0$. So we are left with the problem \begin{align} \max_{x_1 \in {0,1}} f(x_1, x_2^*(x_1), x_3^*(x_1, x_2^*(x_1)), x_4^*(x_1, x_2^*(x_1), x_3(x_1, x_2^*(x_1)))) \end{align} If $x_1 = 0$, then $x_2^*(0) = 1$ , $x_3^*(0,1) = 1$, $x_4^*(0,1,1) = 0$ and if $x_1 = 1$, then $x_2^*(1) = 0$ , $x_3^*(1,0) = 1$, $x_4^*(1,0,1) = 0$. So you would need to compare $f(0,1,1,0) = 4$ and $f(1,0,1,0) = 3$. Sucht that $(0,1,1,0) = \arg\max_x\{f(x) \mid g(x) \leq 0\}$ is immediate.