DP for the multidimensional knapsack problem¶

Part 3 · Dynamic programming · Chapter 22 · Lecture notes, volume 3 (PDF) · Slides · Exercises: Multidimensional knapsack (MDKP)

Prerequisites

From this module, the chapter «DP for the 0/1 knapsack problem»: the recurrence $v(j,k)$ of the 0/1 knapsack problem (KP) over items and capacities, the matrix $s$ of the decisions and the reconstruction of a solution.
From this module, the chapter «Knapsack problems»: the multidimensional knapsack problem, with one capacity $c_d$ and one weight $w_{dj}$ for every dimension $d$.
From the module Algorithms: pseudocode conventions (Chapter 2) and the size of the input (Chapter 11).

Objectives

At the end of this chapter you will be able to:

write the recurrence $v(j,k_1,\dots,k_m)$ over the items and the vector of the capacities;
run the DP algorithm by hand on an instance with $m=2$ dimensions, one matrix for each item;
reconstruct an optimal solution from the tables $s$;
count the $\Theta(m\,n\prod_{d=1}^{m} (c_d+1))$ steps and explain why the number of states grows exponentially with $m$.

The problem of this chapter is the multidimensional knapsack problem (MDKP): its definition and its assumptions are on its page.

22.1 A DP algorithm¶

We write $m$ for the number of dimensions, so $\mathscr{D}=\{1,2,\dots,m\}$, because in the DP chapters the letter $k$ denotes a capacity. Item $j$ has the weight vector $\vet{w}_j=(w_{1j},w_{2j},\dots,w_{mj})$, and the knapsack has the capacity vector $\vet{c}=(c_1,c_2,\dots,c_m)$.
For two vectors, $\vet{w}_j\le\vet{k}$ means $w_{dj}\le k_d$ for every dimension $d\in\mathscr{D}$.
A solution is described by the binary vector $(x_1,x_2,\dots,x_n)$, where $x_j=1$ if item $j$ is selected; it is feasible if $\sum_{j=1}^{n} w_{dj}x_j\le c_d$ for every $d\in\mathscr{D}$.

Example 22.1: MDKP instance

We consider a knapsack with $m=2$ dimensions and capacities $c_1=5$ and $c_2=4$, and a set $\mathscr{I}=\{1,2,3,4\}$ of $4$ items ($n=4$), with the following profits and weights:

\[ \begin{array}{l|rrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} \\ \hline {p_j} & 9 & 8 & 3 & 9 \\ {w_{1j}} & 1 & 4 & 2 & 3 \\ {w_{2j}} & 2 & 1 & 1 & 4 \\ \hline \end{array} \]

We refer to this MDKP instance as Example 22.1.

Step 1: computation of the optimal value
For any $j \in \{0,1,\dots,n\}$ and any vector $\vet{k}=(k_1,k_2,\dots,k_m)$ with $k_d \in \{0,1,\dots,c_d\}$ for every $d\in\mathscr{D}$, let $v(j,\vet{k})=v(j,k_1,\dots,k_m)$ be the optimal value of the MDKP subinstance given by:
1. a knapsack with capacity $k_d$ in each dimension $d\in\mathscr{D}$,
2. a set $\{1,2,\dots,j\}$ of available items,
3. for each item $h \in \{1,2,\dots,j\}$, a profit $p_h$ and a weight vector $\vet{w}_h$.
The recursive formula to compute $v(j,\vet{k})$ reads as follows:

\[\begin{equation*} \label{eq:mdkp} v(j,\vet{k})= \left\{ \begin{array}{ll} 0 & \textrm{if $j=0$,}\\[2ex] v(j-1,\vet{k}) & \begin{array}[t]{@{}l@{}}\textrm{if $j\ge 1$ and}\\ \textrm{$w_{dj}>k_d$ for some $d$,}\end{array}\\[4ex] \begin{array}[t]{@{}l@{}}\displaystyle \max \bigg\{ v(j-1,\vet{k}),\\ \qquad p_j+v(j-1,\vet{k}-\vet{w}_j) \bigg\}\end{array} & \textrm{if $j\ge 1$ and $\vet{w}_j\le\vet{k}$.} \end{array} \right. \tag{22.1} \end{equation*}\]
- With $m=1$ the formula $\eqref{eq:mdkp}$ is the recurrence of the KP: the only change is that the capacity $k$ becomes the vector $\vet{k}$, and «item $j$ fits» means $\vet{w}_j\le\vet{k}$.
- The base cases are $v(0,\vet{k})=0$ for every vector $\vet{k}$, since no item is available.
- The formula generates at most $2$ independent subproblems: item $j$ is not selected, and the residual subproblem has the same vector $\vet{k}$, or it is selected, and the residual subproblem has the vector $\vet{k}-\vet{w}_j$.
  
  $\rightsquigarrow$ Optimal Substructure verified!
- Different decisions on the items $j+1,\dots,n$ can leave the same vector of residual capacities, and therefore the same value $v(j,\vet{k})$ may be needed several times.
  
  $\rightsquigarrow$ Overlapping Subproblems verified!
- The value $v(j,\vet{k})$ depends only on values of row $j-1$. Therefore, the bottom-up approach computes the rows $j=0,1,\dots,n$ in this order, and in each row all the vectors $\vet{k}$ in any order.
- The state of the DP algorithm is the pair $(j,\vet{k})$: for every $j$ the table has one cell for each vector $\vet{k}$, that is, $\prod_{d=1}^{m}(c_d+1)$ cells. With $m=2$ the row $j$ is a matrix, with one row for each $k_1$ and one column for each $k_2$.

Step 2: computation of an optimal solution

For each item $j$ and vector $\vet{k}$ we store $s[j][\vet{k}]=1$ if item $j$ is selected in the optimal solution found for $(j,\vet{k})$, and $s[j][\vet{k}]=0$ otherwise.
The set of all the vectors $\vet{k}$ is $\mathscr{C}=\{0,1,\dots,c_1\}\times\{0,1,\dots,c_2\}\times\dots\times\{0,1,\dots,c_m\}$.

This is the pseudo-code of the DP algorithm using the bottom-up approach, which stores the tables $s$ together with the tables $v$:

Algorithm: MDKP_DP

Input: An MDKP instance given by $n$, $m$, the array $p[1..n]$, the weight vectors $\vet{w}_1,\dots,\vet{w}_n$, and the capacity vector $\vet{c}$

Output: The optimal value of the MDKP instance and the tables $s[j][\vet{k}]$

1Function MDKP_DP($n,m,p,\vet{w},\vet{c}$)

2$v := \textnormal{new array}[0..n][0..c_1]\cdots[0..c_m]$; $s := \textnormal{new array}[0..n][0..c_1]\cdots[0..c_m]$

3for each $\vet{k} \in \mathscr{C}$ do

4$v[0][\vet{k}] \leftarrow 0$; $s[0][\vet{k}] \leftarrow 0$

5end

6for $j := 1$ to $n$ do

7for each $\vet{k} \in \mathscr{C}$ do

8$v[j][\vet{k}] \leftarrow v[j-1][\vet{k}]$; $s[j][\vet{k}] \leftarrow 0$

9if $\vet{w}_j\le\vet{k}$ and $p[j]+v[j-1][\vet{k}-\vet{w}_j] > v[j][\vet{k}]$ then

10$v[j][\vet{k}] \leftarrow p[j]+v[j-1][\vet{k}-\vet{w}_j]$; $s[j][\vet{k}] \leftarrow 1$

11end

12end

13end

14return $v[n][\vet{c}], s$

The structure is the one of the DP algorithm of the KP; the loop over the capacities becomes a loop over all the vectors $\vet{k}\in\mathscr{C}$.
The test $\vet{w}_j\le\vet{k}$ compares $m$ pairs of numbers, and the vector $\vet{k}-\vet{w}_j$ needs $m$ subtractions.
In case of ties item $j$ is not selected, because the value is updated only when it is strictly larger.

Example 22.2: Execution of the DP algorithm

We consider the MDKP instance of Example 22.1, with capacities $c_1=5$ and $c_2=4$. The row $j=0$ is $v[0][\vet{k}]=0$ for every $\vet{k}$. For each item $j$ we compute the matrix $v[j][k_1][k_2]$, with one row for each $k_1\in\{0,1,\dots,5\}$ and one column for each $k_2\in\{0,1,\dots,4\}$.

These are the computations of the cell $\vet{k}=\vet{c}=(5,4)$ for each item, and of the cells used by the reconstruction:

$v[1][(5,4)]=\max\{v[0][(5,4)],\,p_1+v[0][(4,2)]\}=\max\{0,\,9+0\}=9$
$v[1][(1,3)]=\max\{v[0][(1,3)],\,p_1+v[0][(0,1)]\}=\max\{0,\,9+0\}=9$
$v[2][(5,4)]=\max\{v[1][(5,4)],\,p_2+v[1][(1,3)]\}=\max\{9,\,8+9\}=17$
$v[3][(5,4)]=\max\{v[2][(5,4)],\,p_3+v[2][(3,3)]\}=\max\{17,\,3+9\}=17$
$v[4][(5,4)]=\max\{v[3][(5,4)],\,p_4+v[3][(2,0)]\}=\max\{17,\,9+0\}=17$

Item $j=1$, with $p_1=9$ and $\vet{w}_1=(1,2)$:

\[ \begin{array}{l|rrrrr} \hline {v[1][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {0} \\ {k_1=1} & {0} & {0} & {9} & {9} & {9} \\ {k_1=2} & {0} & {0} & {9} & {9} & {9} \\ {k_1=3} & {0} & {0} & {9} & {9} & {9} \\ {k_1=4} & {0} & {0} & {9} & {9} & {9} \\ {k_1=5} & {0} & {0} & {9} & {9} & {9} \\ \hline \end{array} \]

Item $j=2$, with $p_2=8$ and $\vet{w}_2=(4,1)$:

\[ \begin{array}{l|rrrrr} \hline {v[2][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {0} \\ {k_1=1} & {0} & {0} & {9} & {9} & {9} \\ {k_1=2} & {0} & {0} & {9} & {9} & {9} \\ {k_1=3} & {0} & {0} & {9} & {9} & {9} \\ {k_1=4} & {0} & {8} & {9} & {9} & {9} \\ {k_1=5} & {0} & {8} & {9} & {17} & {17} \\ \hline \end{array} \]

Item $j=3$, with $p_3=3$ and $\vet{w}_3=(2,1)$:

\[ \begin{array}{l|rrrrr} \hline {v[3][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {0} \\ {k_1=1} & {0} & {0} & {9} & {9} & {9} \\ {k_1=2} & {0} & {3} & {9} & {9} & {9} \\ {k_1=3} & {0} & {3} & {9} & {12} & {12} \\ {k_1=4} & {0} & {8} & {9} & {12} & {12} \\ {k_1=5} & {0} & {8} & {9} & {17} & {17} \\ \hline \end{array} \]

Item $j=4$, with $p_4=9$ and $\vet{w}_4=(3,4)$:

\[ \begin{array}{l|rrrrr} \hline {v[4][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {0} \\ {k_1=1} & {0} & {0} & {9} & {9} & {9} \\ {k_1=2} & {0} & {3} & {9} & {9} & {9} \\ {k_1=3} & {0} & {3} & {9} & {12} & {12} \\ {k_1=4} & {0} & {8} & {9} & {12} & {12} \\ {k_1=5} & {0} & {8} & {9} & {17} & {17} \\ \hline \end{array} \]

Example 22.3: The tables $s$

For the instance of Example 22.1, these are the matrices $s[j][k_1][k_2]$ computed by the DP algorithm; a $1$ means that item $j$ is selected in the optimal solution found for $(j,k_1,k_2)$.

Item $j=1$, with $p_1=9$ and $\vet{w}_1=(1,2)$:

\[ \begin{array}{l|rrrrr} \hline {s[1][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {0} \\ {k_1=1} & {0} & {0} & {1} & {1} & {1} \\ {k_1=2} & {0} & {0} & {1} & {1} & {1} \\ {k_1=3} & {0} & {0} & {1} & {1} & {1} \\ {k_1=4} & {0} & {0} & {1} & {1} & {1} \\ {k_1=5} & {0} & {0} & {1} & {1} & {1} \\ \hline \end{array} \]

Item $j=2$, with $p_2=8$ and $\vet{w}_2=(4,1)$:

\[ \begin{array}{l|rrrrr} \hline {s[2][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {0} \\ {k_1=1} & {0} & {0} & {0} & {0} & {0} \\ {k_1=2} & {0} & {0} & {0} & {0} & {0} \\ {k_1=3} & {0} & {0} & {0} & {0} & {0} \\ {k_1=4} & {0} & {1} & {0} & {0} & {0} \\ {k_1=5} & {0} & {1} & {0} & {1} & {1} \\ \hline \end{array} \]

Item $j=3$, with $p_3=3$ and $\vet{w}_3=(2,1)$:

\[ \begin{array}{l|rrrrr} \hline {s[3][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {0} \\ {k_1=1} & {0} & {0} & {0} & {0} & {0} \\ {k_1=2} & {0} & {1} & {0} & {0} & {0} \\ {k_1=3} & {0} & {1} & {0} & {1} & {1} \\ {k_1=4} & {0} & {0} & {0} & {1} & {1} \\ {k_1=5} & {0} & {0} & {0} & {0} & {0} \\ \hline \end{array} \]

Item $j=4$, with $p_4=9$ and $\vet{w}_4=(3,4)$:

\[ \begin{array}{l|rrrrr} \hline {s[4][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {0} \\ {k_1=1} & {0} & {0} & {0} & {0} & {0} \\ {k_1=2} & {0} & {0} & {0} & {0} & {0} \\ {k_1=3} & {0} & {0} & {0} & {0} & {0} \\ {k_1=4} & {0} & {0} & {0} & {0} & {0} \\ {k_1=5} & {0} & {0} & {0} & {0} & {0} \\ \hline \end{array} \]

Once the tables $s$ have been computed, an optimal solution is reconstructed by scanning the items from $j=n$ down to $j=1$, starting from $\vet{k}=\vet{c}$ and $x_j=0$ for every item $j$:

\[ x_j \leftarrow s[j][\vet{k}], \qquad \vet{k} \leftarrow \vet{k} - s[j][\vet{k}]\,\vet{w}_j. \]

Algorithm: MDKP_Reconstruct

Input: The number $n$ of items, the capacity vector $\vet{c}$, the weight vectors $\vet{w}_1,\dots,\vet{w}_n$, and the tables $s$

Output: An optimal solution of the MDKP instance

1Function MDKP_Reconstruct($n,\vet{c},\vet{w},s$)

2$x := \textnormal{new array}[1..n]$

3$\vet{k} := \vet{c}$

4for $j := n$ downto $1$ do

5$x[j] \leftarrow s[j][\vet{k}]$

6$\vet{k} \leftarrow \vet{k}-x[j]\,\vet{w}_j$

7end

8return $x$

Example 22.4: Computing an optimal solution

After the execution of the DP algorithm on the instance of Example 22.1, we start from $j=4$ and $\vet{k}=(5,4)$:

Iteration	$j$	$\vet{k}$	$s[j][\vet{k}]$	$x[1]$	$x[2]$	Action
$-$	$-$	$-$	$-$	0	0	$\vet{k}=(5,4)$
$1$	$4$	$(5,4)$	$0$	0	0	$x[4]\leftarrow 0$, $\vet{k}=(5,4)$
$2$	$3$	$(5,4)$	$0$	0	0	$x[3]\leftarrow 0$, $\vet{k}=(5,4)$
$3$	$2$	$(5,4)$	$1$	0	1	$x[2]\leftarrow 1$, $\vet{k}\leftarrow (5,4)-(4,1)=(1,3)$
$4$	$1$	$(1,3)$	$1$	1	1	$x[1]\leftarrow 1$, $\vet{k}\leftarrow (1,3)-(1,2)=(0,1)$

The vector $x=(1,1,0,0)$ is an optimal solution of the MDKP instance of Example 22.1. Its weights are $1+4=5\le c_1$ and $2+1=3\le c_2$, and its optimal value is $v(4,5,4)=17$.

With the first dimension alone, the KP with capacity $c_1=5$ has optimal value $18$, attained by the items $\{1,4\}$; their total weight in the second dimension is $2+4=6>c_2$. Both dimensions must be checked at the same time, as the formula $\eqref{eq:mdkp}$ does.

22.1.1 Number of steps¶

Let $N=|\mathscr{C}|=\prod_{d=1}^{m}(c_d+1)$ be the number of vectors $\vet{k}$, and let $S(n,m,\vet{c})$ denote the number of steps executed by MDKP_DP in the worst case. Lines 9 and 10 work on vectors of $m$ components, so we count $m$ steps for each of their executions:
- Lines 2 and 14 are executed $1$ time each.
- Lines 3 and 4 are executed $N$ times each.
- Line 6 is executed $n$ times.
- Lines 7 and 8 are executed $nN$ times each.
- Lines 9 and 10 are executed at most $nN$ times each, with $m$ steps each.
Therefore, the total number of steps in the worst case is

\[ S(n,m,\vet{c})=2m\,nN+2nN+2N+n+2, \]

and, since $2m\,nN\le S(n,m,\vet{c})\le 9m\,nN$,

\[ S(n,m,\vet{c})=\Theta\Big(m\,n\prod_{d=1}^{m}(c_d+1)\Big). \]

The DP algorithm for the MDKP executes $\Theta(m\,n\prod_{d=1}^{m}(c_d+1))$ steps in the worst case. For a fixed number $m$ of dimensions this is $\Theta(n\prod_{d=1}^{m}c_d)$, a pseudo-polynomial number of steps.
The reconstruction executes $\Theta(m\,n)$ steps.

22.1.2 The curse of dimensionality¶

Each new dimension multiplies the number of states by $c_d+1$. If all the capacities are equal to $c$, the table has $(n+1)(c+1)^m$ cells: the number of states grows exponentially with $m$.
The size of the input grows only linearly with $m$: one more dimension adds $n+1$ numbers, the weights $w_{dj}$ and the capacity $c_d$.
This explosion of the number of states when the state becomes a vector is called the curse of dimensionality.

$m$	cells $(n+1)(c+1)^m$, with $n=50$ and $c=100$
$1$	$5\,151$
$2$	$520\,251$
$3$	$52\,545\,351$
$4$	$5\,307\,080\,451$
$5$	$536\,015\,125\,551$

With $m=1$ the table has a few thousand cells; with $m=5$ it has more than $5\cdot 10^{11}$, too many to be stored. The DP algorithm is therefore useful for the MDKP only when $m$ and the capacities are small.

22.2 Typical mistakes¶

Warning

Checking only one dimension. Item $j$ fits in $\vet{k}$ only if $w_{dj}\le k_d$ for every dimension $d$; one dimension is not enough.
Updating only one capacity. When item $j$ is selected, all the components of $\vet{k}$ decrease, by $\vet{w}_j$.
Solving one KP per dimension. The KP with the capacity $c_d$ alone gives an upper bound, but its optimal solution may violate another dimension.
Calling the DP algorithm polynomial. Its number of steps contains the product of the capacities, which is exponential in $m$ and in the size of the capacities.

22.3 In summary¶

In summary

The recurrence of the KP extends to the MDKP by replacing the capacity $k$ with the vector $\vet{k}=(k_1,\dots,k_m)$: $v(j,\vet{k})=\max\{v(j-1,\vet{k}),\,p_j+v(j-1,\vet{k}-\vet{w}_j)\}$ when $\vet{w}_j\le\vet{k}$.
The table has $(n+1)\prod_{d=1}^{m}(c_d+1)$ cells and the DP algorithm executes $\Theta(m\,n\prod_{d=1}^{m}(c_d+1))$ steps, that is, $\Theta(n\prod_{d=1}^{m}c_d)$ for a fixed $m$.
The number of states grows exponentially with $m$: the curse of dimensionality.
The tables $s$ give an optimal solution, read backwards from $(n,\vet{c})$.

Dashboard of the MDKP example. Example 22.1 ($\vet{c}=(5,4)$, four items):

Method	Lower bound	Upper bound	Origin
DP algorithm	$17$	$17$	optimal value, solution $x=(1,1,0,0)$

Exercises on this chapter: Multidimensional knapsack (MDKP)

Iteration	\(j\)	\(\vet{k}\)	\(s[j][\vet{k}]\)	\(x[1]\)	\(x[2]\)	Action
\(-\)	\(-\)	\(-\)	\(-\)	0	0	\(\vet{k}=(5,4)\)
\(1\)	\(4\)	\((5,4)\)	\(0\)	0	0	\(x[4]\leftarrow 0\), \(\vet{k}=(5,4)\)
\(2\)	\(3\)	\((5,4)\)	\(0\)	0	0	\(x[3]\leftarrow 0\), \(\vet{k}=(5,4)\)
\(3\)	\(2\)	\((5,4)\)	\(1\)	0	1	\(x[2]\leftarrow 1\), \(\vet{k}\leftarrow (5,4)-(4,1)=(1,3)\)
\(4\)	\(1\)	\((1,3)\)	\(1\)	1	1	\(x[1]\leftarrow 1\), \(\vet{k}\leftarrow (1,3)-(1,2)=(0,1)\)

\(m\)	cells \((n+1)(c+1)^m\), with \(n=50\) and \(c=100\)
\(1\)	\(5\,151\)
\(2\)	\(520\,251\)
\(3\)	\(52\,545\,351\)
\(4\)	\(5\,307\,080\,451\)
\(5\)	\(536\,015\,125\,551\)