DP for the knapsack problem with setups¶

Part 3 · Dynamic programming · Chapter 23 · Lecture notes, volume 3 (PDF) · Slides · Exercises: Knapsack with setups (KPS)

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 knapsack problem with setups, its classes, setup costs $f_h$ and setup weights $s_h$.
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 of the KPS: for each class, the best value without opening it and the best value after paying its setup;
run the DP algorithm by hand, class by class, with a KP recurrence inside each opened class;
reconstruct an optimal solution from the choice tables $s$ and $o$;
count the $\Theta(nc)$ steps of the DP algorithm.

The problem of this chapter is the knapsack problem with setups (KPS): its definition and its assumptions are on its page.

23.1 A DP algorithm¶

We number the items class by class, so that $\mathscr{J}_h=\{\ell_{h-1}+1,\dots,\ell_h\}$ for every class $h$, with $\ell_0=0$ and $\ell_q=n$. Class $h$ has $t_h=|\mathscr{J}_h|=\ell_h-\ell_{h-1}$ items, and its $i$-th item is $j=\ell_{h-1}+i$.
A solution is described by the binary vector $(x_1,x_2,\dots,x_n)$. Class $h$ is open if at least one of its items is selected: then its setup weight $s_h$ is added to the total weight, and its setup cost $f_h$ is subtracted from the total revenue.

Example 23.1: KPS instance

We consider a knapsack of capacity $c=10$ and a set $\mathscr{I}=\{1,2,\dots,5\}$ of $5$ items ($n=5$), partitioned into $q=2$ classes: $\mathscr{J}_1=\{1,2\}$, with setup cost $f_1=2$ and setup weight $s_1=2$, and $\mathscr{J}_2=\{3,4,5\}$, with setup cost $f_2=3$ and setup weight $s_2=1$. The revenues and weights are:

\[ \begin{array}{l|rr|rrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\ \hline {p_j} & 6 & 5 & 4 & 7 & 3 \\ {w_j} & 3 & 2 & 2 & 4 & 1 \\ \hline \end{array} \]

We refer to this KPS instance as Example 23.1.

Step 1: computation of the optimal value
- The classes are the stages of the DP algorithm. For each class $h$ there are two options: class $h$ stays closed, or class $h$ is opened, its setup is paid, and some of its items are selected.
- Inside an open class, the choice of the items is a KP: the DP algorithm of the KP runs over the items of the class, starting from the value left after paying the setup.
For any $h \in \{0,1,\dots,q\}$ and $k \in \{0,1,\dots,c\}$, let $v(h,k)$ be the optimal value of the KPS subinstance with capacity $k$ and the classes $\mathscr{J}_1,\dots,\mathscr{J}_h$. For any $h \in \{1,\dots,q\}$ and $i \in \{0,1,\dots,t_h\}$, let $u(h,i,k)$ be the optimal value of the same subinstance when class $h$ is open (its setup is paid) and only its first $i$ items are available, with $u(h,i,k)=-\infty$ if the setup weight does not fit.

The recursive formulas to compute $u(h,i,k)$ and $v(h,k)$ read as follows, where $j=\ell_{h-1}+i$ is the $i$-th item of class $h$:

\[\begin{equation*} \label{eq:kpsu} u(h,i,k)= \left\{ \begin{array}{ll} -\infty & \textrm{if $i=0$ and $k<s_h$,}\\[2ex] v(h-1,k-s_h)-f_h & \textrm{if $i=0$ and $k\ge s_h$,}\\[2ex] u(h,i-1,k) & \textrm{if $i\ge 1$ and $w_j>k$,}\\[2ex] \begin{array}[t]{@{}l@{}}\displaystyle \max \bigg\{ u(h,i-1,k),\\ \qquad p_j+u(h,i-1,k-w_j) \bigg\}\end{array} & \textrm{if $i\ge 1$ and $w_j\le k$,} \end{array} \right. \tag{23.1} \end{equation*}\]

\[\begin{equation*} \label{eq:kpsv} v(h,k)= \left\{ \begin{array}{ll} 0 & \textrm{if $h=0$,}\\[2ex] \max \big\{ v(h-1,k),\; u(h,t_h,k) \big\} & \textrm{if $h\ge 1$.} \end{array} \right. \tag{23.2} \end{equation*}\]
- The row $u(h,0,\cdot)$ pays the setup of class $h$: the setup weight $s_h$ leaves the capacity $k-s_h$ to the classes $1,2,\dots,h-1$, and the setup cost $f_h$ is subtracted.
- The rows $u(h,1,\cdot),\dots,u(h,t_h,\cdot)$ are the recurrence of the KP over the items of class $h$, with $-\infty+p_j=-\infty$.
- The formula $\eqref{eq:kpsv}$ compares the two options for class $h$: closed, with value $v(h-1,k)$, or open, with value $u(h,t_h,k)$.
- The row $u(h,0,\cdot)$ allows an open class with no selected item, which is not a solution of the KPS. This value is never chosen in $\eqref{eq:kpsv}$, since $f_h\ge 1$ gives
  
  \[ v(h-1,k-s_h)-f_h\;<\;v(h-1,k). \]
  
  Hence, when the maximum in $\eqref{eq:kpsv}$ is attained only by $u(h,t_h,k)$, at least one item of class $h$ is selected.
- An optimal solution for $(h,k)$ is built from an optimal solution of a smaller subinstance: $(h-1,k)$ if class $h$ is closed, and, inside an open class, $(h,i-1,\cdot)$ with or without item $j$.
  
  $\rightsquigarrow$ Optimal Substructure verified!
- Different decisions on the classes $h+1,\dots,q$ can leave the same capacity $k$, and therefore the same value $v(h,k)$ may be needed several times.
  
  $\rightsquigarrow$ Overlapping Subproblems verified!
- The bottom-up approach computes, for $h=1,2,\dots,q$, first the rows $u(h,i,\cdot)$ for $i=0,1,\dots,t_h$, and then the row $v(h,\cdot)$, each one for increasing $k$. The optimal value of the KPS instance is $v(q,c)$.

Step 2: computation of an optimal solution

Two choice tables are stored: $s[h][i][k]=1$ if the $i$-th item of class $h$ is selected in the optimal value $u[h][i][k]$, and $o[h][k]=1$ if class $h$ is open in the optimal value $v[h][k]$.
The setup weight $s_h$ has one index; the choice $s[h][i][k]$ has three.

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

Algorithm: KPS_DP

Input: A KPS instance given by $q$, the classes $\mathscr{J}_1,\dots,\mathscr{J}_q$ numbered as above, the setup costs $f_h$ and weights $s_h$, arrays $p[1..n]$, $w[1..n]$, and capacity $c$

Output: The optimal value of the KPS instance and the choice tables $s$ and $o$

1Function KPS_DP($q,\mathscr{J},p,w,c$)

2$v,o := \textnormal{new arrays}[0..q][0..c]$; $u,s := \textnormal{new arrays}[1..q][0..t_h][0..c]$

3for $k := 0$ to $c$ do

4$v[0][k] \leftarrow 0$; $o[0][k] \leftarrow 0$

5end

6for $h := 1$ to $q$ do

7for $k := 0$ to $c$ do

8$u[h][0][k] \leftarrow -\infty$

9if $k\ge s_h$ then

10$u[h][0][k] \leftarrow v[h-1][k-s_h]-f_h$

11end

12end

13for $i := 1$ to $t_h$ do

14$j := \ell_{h-1}+i$

15for $k := 0$ to $c$ do

16$u[h][i][k] \leftarrow u[h][i-1][k]$; $s[h][i][k] \leftarrow 0$

17if $w[j]\le k$ and $p[j]+u[h][i-1][k-w[j]] > u[h][i][k]$ then

18$u[h][i][k] \leftarrow p[j]+u[h][i-1][k-w[j]]$; $s[h][i][k] \leftarrow 1$

19end

20end

21end

22for $k := 0$ to $c$ do

23$v[h][k] \leftarrow v[h-1][k]$; $o[h][k] \leftarrow 0$

24if $u[h][t_h][k] > v[h][k]$ then

25$v[h][k] \leftarrow u[h][t_h][k]$; $o[h][k] \leftarrow 1$

26end

27end

28end

29return $v[q][c], s, o$

For each class, the first loop over $k$ pays the setup where it fits, the loops over $i$ and $k$ run the DP algorithm of the KP over the items of the class, and the last loop over $k$ compares the closed and the open class.
In case of ties the item is not selected and the class stays closed, because the values are updated only when they are strictly larger.

Example 23.2: Execution of the DP algorithm

We consider the KPS instance of Example 23.1. The rows are computed in the order of the table below, each one for $k=0,1,\dots,10$; these are some of the computations:

$u[1][0][1]=-\infty$, since $k=1<s_1=2$
$v[1][7]=\max\{v[0][7],\,u[1][2][7]\}=\max\{0,\,9\}=9$
$v[2][10]=\max\{v[1][10],\,u[2][3][10]\}=\max\{9,\,11\}=11$
$u[2][3][10]=\max\{u[2][2][10],\,p_5+u[2][2][9]\}=\max\{10,\,3+8\}=11$
$u[2][2][9]=\max\{u[2][1][9],\,p_4+u[2][1][5]\}=\max\{6,\,7+1\}=8$
$u[2][1][5]=\max\{u[2][0][5],\,p_3+u[2][0][3]\}=\max\{0,\,4-3\}=1$
$u[2][0][3]=v[1][2]-f_2=0-3=-3$
$v[1][2]=\max\{v[0][2],\,u[1][2][2]\}=\max\{0,\,-2\}=0$

This is the table of the values after the execution of the DP algorithm, row by row in the order of computation:

Row	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$	$k=9$	$k=10$
$v[0][k]$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$u[1][0][k]$ (setup)	$-\infty$	$-\infty$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$
$u[1][1][k]$ ($j=1$)	$-\infty$	$-\infty$	$-2$	$-2$	$-2$	$4$	$4$	$4$	$4$	$4$	$4$
$u[1][2][k]$ ($j=2$)	$-\infty$	$-\infty$	$-2$	$-2$	$3$	$4$	$4$	$9$	$9$	$9$	$9$
$v[1][k]$	$0$	$0$	$0$	$0$	$3$	$4$	$4$	$9$	$9$	$9$	$9$
$u[2][0][k]$ (setup)	$-\infty$	$-3$	$-3$	$-3$	$-3$	$0$	$1$	$1$	$6$	$6$	$6$
$u[2][1][k]$ ($j=3$)	$-\infty$	$-3$	$-3$	$1$	$1$	$1$	$1$	$4$	$6$	$6$	$10$
$u[2][2][k]$ ($j=4$)	$-\infty$	$-3$	$-3$	$1$	$1$	$4$	$4$	$8$	$8$	$8$	$10$
$u[2][3][k]$ ($j=5$)	$-\infty$	$-3$	$0$	$1$	$4$	$4$	$7$	$8$	$11$	$11$	$11$
$v[2][k]$	$0$	$0$	$0$	$1$	$4$	$4$	$7$	$9$	$11$	$11$	$11$

The optimal value of the instance is $v[2][10]=11$. The values $-2$ and $-3$ in the setup rows are the setup costs paid before any item is selected.

Example 23.3: The choice tables

For the instance of Example 23.1, these are the choice tables computed by the DP algorithm: the rows $s[h][i][\cdot]$ of the items, and the rows $o[h][\cdot]$ of the classes.

Row	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$	$k=9$	$k=10$
$s[1][1][k]$ ($j=1$)	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$
$s[1][2][k]$ ($j=2$)	$0$	$0$	$0$	$0$	$1$	$0$	$0$	$1$	$1$	$1$	$1$
$o[1][k]$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$s[2][1][k]$ ($j=3$)	$0$	$0$	$0$	$1$	$1$	$1$	$0$	$1$	$0$	$0$	$1$
$s[2][2][k]$ ($j=4$)	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$0$
$s[2][3][k]$ ($j=5$)	$0$	$0$	$1$	$0$	$1$	$0$	$1$	$0$	$1$	$1$	$1$
$o[2][k]$	$0$	$0$	$0$	$1$	$1$	$0$	$1$	$0$	$1$	$1$	$1$

An optimal solution is reconstructed by scanning the classes from $h=q$ down to $h=1$, starting from $k=c$ and $x_j=0$ for every item $j$.
If $o[h][k]=0$, class $h$ is closed and $k$ does not change. If $o[h][k]=1$, the items of class $h$ are scanned from $i=t_h$ down to $i=1$ as in the KP, and at the end the setup weight $s_h$ is subtracted from $k$.

Algorithm: KPS_Reconstruct

Input: The number $q$ of classes, the setup weights $s_h$, the array $w[1..n]$, the capacity $c$, and the choice tables $s$ and $o$

Output: An optimal solution of the KPS instance

1Function KPS_Reconstruct($q,w,c,s,o$)

2$x := \textnormal{new array}[1..n]$, with $x[j]=0$ for every $j$

3$k := c$

4for $h := q$ downto $1$ do

5if $o[h][k]=1$ then

6for $i := t_h$ downto $1$ do

7$j := \ell_{h-1}+i$; $x[j] \leftarrow s[h][i][k]$

8$k \leftarrow k-x[j]\,w[j]$

9end

10$k \leftarrow k-s_h$

11end

12end

13return $x$

Example 23.4: Computing an optimal solution

After the execution of the DP algorithm on the instance of Example 23.1, we start from $h=2$ and $k=10$:

Iteration	Stage	$k$	Choice	$x[3]$	$x[4]$	$x[5]$	Action
$-$	$-$	$-$	$-$	0	0	0	$k=10$
$1$	$h=2$	$10$	$o[2][10]=1$	0	0	0	class $2$ open
$2$	$j=5$	$10$	$s[2][3][10]=1$	0	0	1	$k\leftarrow 10-1=9$
$3$	$j=4$	$9$	$s[2][2][9]=1$	0	1	1	$k\leftarrow 9-4=5$
$4$	$j=3$	$5$	$s[2][1][5]=1$	1	1	1	$k\leftarrow 5-2=3$
$-$	$-$	$3$	$-$	1	1	1	setup: $k\leftarrow 3-s_2=2$
$5$	$h=1$	$2$	$o[1][2]=0$	1	1	1	class $1$ closed

The vector $x=(0,0,1,1,1)$ is an optimal solution of the KPS instance of Example 23.1: only class $2$ is open, and the items $\{3,4,5\}$ are selected. Its total weight is $2+4+1+s_2=8\le c$ and its optimal value is $v(2,10)=4+7+3-f_2=11$.

The items of class $1$ have the larger ratio between total revenue and total weight ($11/5$ against $14/7$), but class $1$ stays closed. With class $1$ alone the best value is $v[1][10]=9$, while the open class $2$ gives $u[2][3][10]=11$; after its items and its setup weight only $k=2$ is left for class $1$, and $o[1][2]=0$.

23.1.1 Number of steps¶

Let $S(n,q,c)$ denote the number of steps executed by KPS_DP in the worst case. The loops over $i$ run over the items of each class, so over all the classes they run $t_1+t_2+\dots+t_q=n$ times. Assuming that the conditions at lines 9, 17 and 24 are always true:
- Lines 2 and 29 are executed $1$ time each.
- Lines 3 and 4 are executed $c+1$ times each.
- Line 6 is executed $q$ times.
- Lines 7, 8, 9, 10, 22, 23, 24 and 25 are executed $q(c+1)$ times each.
- Lines 13 and 14 are executed $n$ times each.
- Lines 15, 16, 17 and 18 are executed $n(c+1)$ times each.
Therefore, the total number of steps in the worst case is

\[ S(n,q,c)=4n(c+1)+8q(c+1)+2n+q+2c+4. \]

Since every class contains at least one item, $1\le q\le n$, and

\[ 4n(c+1)\;\le\; S(n,q,c)\;\le\; 12n(c+1)+3n+2c+4. \]

Both bounds are $\Theta(nc)$, hence $S(n,q,c)=\Theta(nc)$.

The DP algorithm for the KPS executes $S(n,q,c)=\Theta(nc)$ steps in the worst case: the setups add $2q$ rows to the $n$ rows of the KP recurrence.
The reconstruction executes $\Theta(n)$ steps.

23.2 Typical mistakes¶

Warning

Paying the setup for every item. The setup of class $h$ is paid once, in the row $u(h,0,\cdot)$; the rows of the items add only $p_j$ and $w_j$.
Starting the items of a class from $v(h-1,k)$. The rows of an open class start from $v(h-1,k-s_h)-f_h$: starting from $v(h-1,k)$ would select items without paying the setup.
Forgetting the setup weight in the reconstruction. After the items of an open class, the capacity decreases also by $s_h$.
Confusing $s_h$ with $s[h][i][k]$. The setup weight of class $h$ has one index; the choice of the $i$-th item of class $h$ has three.

23.3 In summary¶

In summary

For each class $h$ the DP algorithm compares the closed class, $v(h-1,k)$, with the open class, $u(h,t_h,k)$.
The open class starts from $u(h,0,k)=v(h-1,k-s_h)-f_h$, which pays the setup once, and continues with the KP recurrence over its items.
The choice tables $s$ (items) and $o$ (classes) give an optimal solution, read backwards from $(q,c)$.
The DP algorithm executes $\Theta(nc)$ steps, as the DP algorithm of the KP.

Dashboard of the KPS example. Example 23.1 ($c=10$, two classes):

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

Exercises on this chapter: Knapsack with setups (KPS)

Row	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)	\(k=5\)	\(k=6\)	\(k=7\)	\(k=8\)	\(k=9\)	\(k=10\)
\(v[0][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(u[1][0][k]\) (setup)	\(-\infty\)	\(-\infty\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)
\(u[1][1][k]\) (\(j=1\))	\(-\infty\)	\(-\infty\)	\(-2\)	\(-2\)	\(-2\)	\(4\)	\(4\)	\(4\)	\(4\)	\(4\)	\(4\)
\(u[1][2][k]\) (\(j=2\))	\(-\infty\)	\(-\infty\)	\(-2\)	\(-2\)	\(3\)	\(4\)	\(4\)	\(9\)	\(9\)	\(9\)	\(9\)
\(v[1][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(3\)	\(4\)	\(4\)	\(9\)	\(9\)	\(9\)	\(9\)
\(u[2][0][k]\) (setup)	\(-\infty\)	\(-3\)	\(-3\)	\(-3\)	\(-3\)	\(0\)	\(1\)	\(1\)	\(6\)	\(6\)	\(6\)
\(u[2][1][k]\) (\(j=3\))	\(-\infty\)	\(-3\)	\(-3\)	\(1\)	\(1\)	\(1\)	\(1\)	\(4\)	\(6\)	\(6\)	\(10\)
\(u[2][2][k]\) (\(j=4\))	\(-\infty\)	\(-3\)	\(-3\)	\(1\)	\(1\)	\(4\)	\(4\)	\(8\)	\(8\)	\(8\)	\(10\)
\(u[2][3][k]\) (\(j=5\))	\(-\infty\)	\(-3\)	\(0\)	\(1\)	\(4\)	\(4\)	\(7\)	\(8\)	\(11\)	\(11\)	\(11\)
\(v[2][k]\)	\(0\)	\(0\)	\(0\)	\(1\)	\(4\)	\(4\)	\(7\)	\(9\)	\(11\)	\(11\)	\(11\)

Row	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)	\(k=5\)	\(k=6\)	\(k=7\)	\(k=8\)	\(k=9\)	\(k=10\)
\(s[1][1][k]\) (\(j=1\))	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(s[1][2][k]\) (\(j=2\))	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)
\(o[1][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(s[2][1][k]\) (\(j=3\))	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(0\)	\(1\)	\(0\)	\(0\)	\(1\)
\(s[2][2][k]\) (\(j=4\))	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(0\)
\(s[2][3][k]\) (\(j=5\))	\(0\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(1\)	\(1\)
\(o[2][k]\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(1\)	\(1\)

Iteration	Stage	\(k\)	Choice	\(x[3]\)	\(x[4]\)	\(x[5]\)	Action
\(-\)	\(-\)	\(-\)	\(-\)	0	0	0	\(k=10\)
\(1\)	\(h=2\)	\(10\)	\(o[2][10]=1\)	0	0	0	class \(2\) open
\(2\)	\(j=5\)	\(10\)	\(s[2][3][10]=1\)	0	0	1	\(k\leftarrow 10-1=9\)
\(3\)	\(j=4\)	\(9\)	\(s[2][2][9]=1\)	0	1	1	\(k\leftarrow 9-4=5\)
\(4\)	\(j=3\)	\(5\)	\(s[2][1][5]=1\)	1	1	1	\(k\leftarrow 5-2=3\)
\(-\)	\(-\)	\(3\)	\(-\)	1	1	1	setup: \(k\leftarrow 3-s_2=2\)
\(5\)	\(h=1\)	\(2\)	\(o[1][2]=0\)	1	1	1	class \(1\) closed