Skip to content

9.12 An ILP model for the Knapsack Problem with Setups

Part 2 · Formulations and their properties · Chapter 9 · Chapter 9: Knapsack problems · Lecture notes, volume 2 (PDF) · Slides · Exercises: Knapsack problems · App: LP relaxation and upper bounds for the 0/1 KP

The Knapsack Problem with Setups and its reference instance (Example 2.8) are defined in Chapter 2 «Knapsack problems», Section 2.9.

  • We introduce the following \(n\) binary variables:

    \[\begin{equation*} \label{BIN_VAR_KPS} x_j = \left\{ \begin{array}{ll} 1 & \textrm{if item $j$ is selected in the knapsack}\\[1.5ex] 0 & \textrm{otherwise} \end{array} \qquad \forall j \in \mathscr{I}. \right. \tag{9.32} \end{equation*}\]

  • We introduce the following \(q\) binary variables:

    \[\begin{equation*} \label{BIN_VAR_KPS_Y} y_h = \left\{ \begin{array}{ll} 1 & \textrm{if class $h$ is activated (its setup is paid)}\\[1.5ex] 0 & \textrm{otherwise} \end{array} \qquad \forall h \in \{1,2,\dots,q\}. \right. \tag{9.33} \end{equation*}\]

Using these variables, an Integer Linear Programming (ILP) model for the Knapsack Problem with Setups (KPS) reads as follows:

\[\begin{align*} && \max \;\;{\sum_{j \in \mathscr{I}} p_j \, x_j - \sum_{h=1}^{q} f_h \, y_h} \label{obj_KPS} \tag{9.34a}\\[1ex] && \text{subject to} \quad {\sum_{j \in \mathscr{I}} w_j \, x_j + \sum_{h=1}^{q} s_h \, y_h} &\leq c, \label{cons1_KPS} \tag{9.34b}\\[1ex] && x_j &\leq y_h, & \forall h \in \{1,2,\dots,q\},~\forall j \in \mathscr{J}_h, \label{cons2_KPS} \tag{9.34c}\\[1ex] &&x_j &\in \{0,1\}, & \forall j \in \mathscr{I}, \label{cons3_KPS} \tag{9.34d}\\[1ex] &&y_h &\in \{0,1\}, & \forall h \in \{1,2,\dots,q\}. \label{cons4_KPS} \tag{9.34e} \end{align*}\]

This ILP model is referred to as the \(\mathrm{ILP}_{\mathrm{KPS}}\) model.

  • Description of the objective function and constraints of the \(\mathrm{ILP}_{\mathrm{KPS}}\) model:

    • the linear objective function \(\eqref{obj_KPS}\) maximizes the total revenue of the selected items minus the setup costs of the activated classes;

    • constraint \(\eqref{cons1_KPS}\) ensures that the total weight of the selected items plus the setup weights of the activated classes does not exceed the knapsack capacity (one linear constraint);

    • constraints \(\eqref{cons2_KPS}\) ensure that an item can be selected only if its class is activated (\(n\) linear constraints, one for each item);

    • finally, constraints \(\eqref{cons3_KPS}\) and \(\eqref{cons4_KPS}\) define the variables of the ILP model.

Example 9.16: \(\mathrm{ILP}_{\mathrm{KPS}}\) model

We consider a knapsack of capacity \(c = 20\) and a set \(\mathscr{I} = \{1,2,3,4,5,6\}\) of \(6\) items (\(n = 6\)), partitioned into \(q = 2\) classes \(\mathscr{J}_1 = \{1,2,3\}\) and \(\mathscr{J}_2 = \{4,5,6\}\), with setup costs \(f_1 = 3\), \(f_2 = 4\), setup weights \(s_1 = 2\), \(s_2 = 3\), and the following revenues and weights:

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

This is the KPS instance of Example 2.8. The \(\mathrm{ILP}_{\mathrm{KPS}}\) model for this KPS instance is:

\[ \begin{array}{rrrrrrrrrrr} {\max} & 6 \, {x_1} & + 8 \, {x_2} & + 5 \, {x_3} & + 7 \, {x_4} & + 9 \, {x_5} & + 4 \, {x_6} & {-} 3 \, {y_1} & {-} 4 \, {y_2} & & \\[0.5ex] \text{subject to} & 4 \, {x_1} & + 5 \, {x_2} & + 3 \, {x_3} & + 6 \, {x_4} & + 7 \, {x_5} & + 2 \, {x_6} & + 2 \, {y_1} & + 3 \, {y_2} & {\le} & 20 \\[0.5ex] & {x_1} & & & & & & {-} {y_1} & & {\le} & 0 \\[0.5ex] & & {x_2} & & & & & {-} {y_1} & & {\le} & 0 \\[0.5ex] & & & {x_3} & & & & {-} {y_1} & & {\le} & 0 \\[0.5ex] & & & & {x_4} & & & & {-} {y_2} & {\le} & 0 \\[0.5ex] & & & & & {x_5} & & & {-} {y_2} & {\le} & 0 \\[0.5ex] & & & & & & {x_6} & & {-} {y_2} & {\le} & 0 \\[0.5ex] & {x_1}, & {x_2}, & {x_3}, & {x_4}, & {x_5}, & {x_6} & & & { \in} & { \{0,1\}} \\[0.5ex] & & & & & & & {y_1}, & {y_2} & { \in} & { \{0,1\}} \end{array} \]

An optimal solution \(~{\tilde{\vet x}}(\mathrm{ILP}_{\mathrm{KPS}})\), \(~{\tilde{\vet y}}(\mathrm{ILP}_{\mathrm{KPS}})\) is:

\[ \tilde x_1=\tilde x_2=\tilde x_3=1,~~\tilde x_4=\tilde x_5=0,~~\tilde x_6=1,~~\tilde y_1=\tilde y_2=1 \]

The optimal value \(z(\mathrm{ILP}_{\mathrm{KPS}})\) is \(16\). The associated optimal solution of the KPS is \(\tilde{S} =\{1,2,3,6\}\). The optimal solution is not unique: the subsets \(\{1,2,3\}\) and \(\{4,5,6\}\) have the same value.

9.13 Typical mistakes

Warning

  • Forgetting to sort the items. The formulas (9.13), (9.14) and the bounds hold only if the items are sorted by non-increasing efficiency: with another order the vector (9.13) is feasible but not optimal.

  • Using \(z(\mathrm{LP}\text{-}0_{\mathrm{KP}})\) as the bound. The first relaxation has no upper bounds on the variables, and it is much weaker: in Example 9.1 it gives \(27\), against \(\tfrac{49}{3}\) for the second relaxation.

  • Rounding when the profits are not integer. The bounds \(\UB_{\mathrm{D}}\) and \(\UB_{\mathrm{MT}}\) round down the fractional part: this is valid only because all the profits are integer.

  • Confusing the split item with the last selected item. The split item \(s\) is the first item that does not fit: in Example 9.1 it is \(s=3\), while the items \(1\) and \(2\) are selected entirely.

  • Assuming that the LP optimum is unique. With items of equal efficiency the \(\mathrm{LP}_{\mathrm{KP}}\) problem has other optimal solutions; the formulas (9.13) give one of them.

  • Copying the \(\mathrm{ILP}_{\mathrm{KP}}\) model to the variants. In the BKP and in the UKP the variables are integer, not binary; in the MCKP the class constraints (9.31c) are equalities; in the KPS, without the constraints \(\eqref{cons2_KPS}\) the model selects items with \(y_h = 0\) and never pays a setup.

9.14 In summary

In summary

  • The \(\mathrm{ILP}_{\mathrm{KP}}\) model has one binary variable per item, one capacity constraint and the objective of maximizing the total profit.

  • The relaxation \(\mathrm{LP}_{\mathrm{KP}}\) is solved by sorting the items by non-increasing efficiency: the items before the split item are selected, the split item is taken fractionally, the others are discarded.

  • The dual of \(\mathrm{LP}_{\mathrm{KP}}\) has the optimal solution \(\tilde{\pi} = p_s/w_s\), and \(z(\mathrm{LP}_{\mathrm{KP}})\) is never larger than twice \(z(\mathrm{ILP}_{\mathrm{KP}})\).

  • Rounding down \(z(\mathrm{LP}_{\mathrm{KP}})\) gives the Dantzig bound; the Martello-Toth bound considers separately the split item out and in.

  • Each variant of Chapter 2 «Knapsack problems» changes one ingredient of the \(\mathrm{ILP}_{\mathrm{KP}}\) model: integer variables (BKP, UKP), one capacity constraint per dimension (MDKP), one variable per item and knapsack (MKP), one equality per class (MCKP), setup variables \(y_h\) with \(x_j \le y_h\) (KPS); the SSP is the KP with \(p_j = w_j\).

Dashboard of Example 9.1. Upper bounds on \(z(\mathrm{ILP}_{\mathrm{KP}})\) computed in this chapter:

Bound Value From
First relaxation \(27\) \(z(\mathrm{LP}\text{-}0_{\mathrm{KP}})\), item \(1\) with \(\tfrac{9}{2}\) copies
Second relaxation \(\tfrac{49}{3}\) \(z(\mathrm{LP}_{\mathrm{KP}})\), split item \(s=3\)
Dantzig bound \(16\) \(\lfloor \tfrac{49}{3} \rfloor\)
Martello-Toth bound \(16\) \(\max\{16, 15\}\)
Optimal value \(15\) solution \(\{1,4\}\) of the \(\mathrm{ILP}_{\mathrm{KP}}\) model

The gap between the best upper bound (\(16\)) and the optimal value (\(15\)) is closed by the exact algorithms of the following chapters.

Exercises on this chapter: Knapsack problems