Exercises · Knapsack problems

Exercises · Chapter 2 · each solution opens with a click · Chapter 2: Knapsack problems · Exercises, volume 1 (PDF)

Exercise 2.1: Feasibility, value and bounds (KP)

We consider the knapsack instance with capacity \(c=12\) and \(n=5\) items, \(\mathscr{I}=\{1,\dots,5\}\), with the following profits and weights:

\[ \begin{array}{l|ccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\[1ex] \hline {p_j} & {6} & {12} & {5} & {13} & {8} \\[1ex] {w_j} & {3} & {4} & {5} & {6} & {8} \\ \hline \end{array} \]

Questions

1. Check the two assumptions on the data of the KP.

2. For each of the subsets \(S_1=\{1,2,5\}\), \(S_2=\{2,4\}\), \(S_3=\{1,2,3\}\), compute the total weight, decide whether it is feasible and, if so, give its profit.

3. Compute the cardinality bound \(\bar k\) and the dual bound it gives.

4. Compute the dual bound of the continuous relaxation (the items can be taken fractionally, in order of non-increasing efficiency) and round it.

5. Find an optimal solution by listing the feasible subsets, and compute the gap between the best dual bound and \(z(I)\).

Solution

1. The total weight is \(3+4+5+6+8=26>12\), so not all the items fit; the heaviest item weighs \(8\le 12\), so every item fits alone. Both assumptions hold.

2. • \(S_1\): weight \(3+4+8=15>12\), not feasible;

   • \(S_2\): weight \(4+6=10\le 12\), feasible, profit \(12+13=25\);

   • \(S_3\): weight \(3+4+5=12\le 12\), feasible, profit \(6+12+5=23\);

3. The weights in non-decreasing order are \(3, 4, 5, 6, 8\): the \(3\) lightest items weigh \(3+4+5=12\le 12\), the \(4\) lightest weigh \(18>12\). Hence \(\bar k=3\): a feasible subset has at most \(3\) items, and the \(3\) largest profits give

   \[ \mathrm{UB}=13+12+8=33. \]

4. The efficiencies are \(\frac{6}{3}=2,\ \frac{12}{4}=3,\ \frac{5}{5}=1,\ \frac{13}{6},\ \frac{8}{8}=1\), so the order is \(2,4,1,3,5\). Items \(2, 4\) weigh \(10\), and the fraction \(\frac{2}{3}\) of item \(1\) fills the residual capacity \(2\):

   \[ \mathrm{UB}=12+13+\frac{2}{3}\cdot 6=29. \]

   The profits are integer, so \(\mathrm{UB}=\lfloor 29\rfloor=29\); it is stronger than the cardinality bound.

5. There are \(15\) feasible subsets:

   \(S\)	weight	profit	\(S\)	weight	profit
   \(\emptyset\)	\(0\)	\(0\)	\(\{1,4\}\)	\(9\)	\(19\)
   \(\{1\}\)	\(3\)	\(6\)	\(\{1,5\}\)	\(11\)	\(14\)
   \(\{2\}\)	\(4\)	\(12\)	\(\{2,3\}\)	\(9\)	\(17\)
   \(\{3\}\)	\(5\)	\(5\)	\(\{2,4\}\)	\(10\)	\(\mathbf{25}\)
   \(\{4\}\)	\(6\)	\(13\)	\(\{2,5\}\)	\(12\)	\(20\)
   \(\{5\}\)	\(8\)	\(8\)	\(\{3,4\}\)	\(11\)	\(18\)
   \(\{1,2\}\)	\(7\)	\(18\)	\(\{1,2,3\}\)	\(12\)	\(23\)
   \(\{1,3\}\)	\(8\)	\(11\)

   The optimal solution is \(\tilde S=\{2,4\}\), the only one with profit \(z(I)=25\):

   

   The gap between the continuous bound and the optimum is \(29-25=4\): the bound alone does not certify the optimum, the enumeration does.

The optimal solution is \(\tilde S=\{2,4\}\) with \(z(I)=25\); the dual bounds are \(33\) (cardinality) and \(29\) (continuous relaxation).

Exercise 2.2: Subset sum and its solution as a KP (SSP)

We consider the subset sum instance with \(n=6\) items and the weights

\[ \begin{array}{l|cccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} \\[1ex] \hline {w_j} & {5} & {14} & {3} & {6} & {15} & {4} \\ \hline \end{array} \]

with the target value \(c=15\).

Questions

1. Check the two assumptions of the SSP.

2. Is the subset \(\{1,4,6\}\) feasible? And the subset \(\{3,4,6\}\)?

3. Find all the feasible subsets for the target \(c=15\), with a short justification.

4. Now the target is \(c=16\). Solve the instance as a KP with \(p_j=w_j\) and give the answer to the SSP.

Solution

1. The total weight is \(47\ge 15\) and the heaviest item weighs \(15\le 15\): both assumptions hold.

2. \(w_1+w_4+w_6=5+6+4=15=15\): feasible. \(w_3+w_4+w_6=3+6+4=13\neq 15\): not feasible.

3. We look at the subsets by their heaviest item, in the order \(5, 2, 4, 1, 6, 3\) of non-increasing weight.

   • Item \(5\) (weight \(15\)) reaches the target alone: \(\{5\}\).

   • Item \(2\) (weight \(14\)) leaves \(1\), and no item weighs \(1\).

   • Without items \(5\) and \(2\) the remaining weights \(6, 5, 4, 3\) sum up to \(18\): a subset of them weighs \(15\) exactly when the items left out weigh \(3\), and the only such choice is to leave out item \(3\). This gives \(\{1,4,6\}\): \(5+6+4=15\).

   The feasible subsets are \(\{5\}\) and \(\{1,4,6\}\): the answer is yes.

4. With \(p_j=w_j\) the KP maximizes the total weight of a subset with weight at most \(16\). No subset weighs \(16\):

   • with item \(5\) or item \(2\) we need \(1\) or \(2\) more, and no item weighs so;

   • without them, the items left out should weigh \(18-16=2\), less than the lightest weight \(3\).

   The best subsets weigh \(z=15\), for example \(\{5\}\). Since \(z=15<16\), the answer to the SSP with target \(16\) is no.

Target \(15\): yes, with \(\{5\}\) and \(\{1,4,6\}\). Target \(16\): no, the KP with \(p_j=w_j\) reaches at most \(15\).

Exercise 2.3: Copies of the items (BKP and UKP)

We consider \(n=3\) items with the following profits, weights and available copies, and a knapsack of capacity \(c=10\):

\[ \begin{array}{l|ccc} \hline & {j=1} & {j=2} & {j=3} \\[1ex] \hline {p_j} & {4} & {13} & {13} \\[1ex] {w_j} & {3} & {5} & {2} \\[1ex] {b_j} & {1} & {2} & {2} \\ \hline \end{array} \]

Questions

1. Check the assumptions of the BKP and write the extended set of items \(\hat{\mathscr{I}}\).

2. A solution of the BKP is the vector \((x_1,x_2,x_3)\) of the numbers of copies, with \(0\le x_j\le b_j\). How many such vectors are there? Is \((1,1,1)\) feasible? And \((0,2,1)\)?

3. Find an optimal solution of the BKP by enumeration, with a short justification.

4. Now the items are available in an unlimited number of copies (UKP). Compute the maximum feasible numbers of copies \(\hat b_j\), the number of candidate vectors, and an optimal solution.

Solution

1. \(\sum_j b_j w_j=1\cdot 3+2\cdot 5+2\cdot 2=17>10\); every item fits (\(w_j\le 10\)) and so do all its copies: \(b_jw_j=3, 10, 4\le 10\). The extended set has \(\sum_j b_j=5\) copies:

   \[ \hat{\mathscr{I}}=\{(1,1),(2,1),(2,2),(3,1),(3,2)\}. \]

2. There are \(\prod_j (b_j+1)=2\cdot 3\cdot 3=18\) vectors, of which \(12\) are feasible. The vector \((1,1,1)\) weighs \(10\le 10\), feasible, profit \(30\); the vector \((0,2,1)\) weighs \(12\), not feasible.

3. Item \(3\) has the largest efficiency, \(\frac{13}{2}\), and item \(2\) the second, \(\frac{13}{5}\). Taking all the copies of items \(3\) and \(2\) would weigh \(14>10\). With \(x_3=2\) (weight \(4\)) the residual capacity \(6\) holds one copy of item \(2\), and the last \(1\) units hold nothing. The enumeration of the \(12\) feasible vectors confirms that \(\tilde x=(0,1,2)\), of weight \(9\), is the only optimal solution, with \(z(I)=39\).

4. \(\hat b_j=\lfloor c/w_j\rfloor\) gives \(\hat b=(3,2,5)\), and there are \(\prod_j(\hat b_j+1)=4\cdot 3\cdot 6=72\) candidate vectors, \(20\) of them feasible. Item \(3\) is the most efficient and its weight \(2\) divides \(c=10\): the solution \(\tilde x=(0,0,5)\) fills the knapsack with the most efficient item, so no solution has a larger profit than \(\frac{13}{2}\cdot 10=65\). It is the only optimal solution, \(z(I)=65\).

BKP: \(\tilde x=(0,1,2)\), \(z(I)=39\). UKP: \(\tilde x=(0,0,5)\), \(z(I)=65\). More copies can only increase the optimal value.

Exercise 2.4: Two knapsacks (MKP)

We consider the multiple knapsack instance with \(m=2\) knapsacks of capacities \(c_1=10\) and \(c_2=6\), and \(n=5\) items with the following profits and weights:

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

Questions

1. Can all the items be inserted? How many candidate solutions are there, if each item goes into one of the knapsacks or into none?

2. Is the solution \(S_1=\{1,2,3\}\), \(S_2=\{4,5\}\) feasible? What is its profit?

3. Every feasible solution of the MKP is also a feasible solution of a KP with capacity \(c_1+c_2=16\). Use this to compute a dual bound.

4. Find an optimal solution of the MKP.

Solution

1. The total weight is \(18>c_1+c_2=16\): not all the items can be inserted. Every item has \(m+1=3\) choices, so there are \(3^5=243\) candidate solutions; \(100\) of them are feasible.

2. \(S_1\) weighs \(2+5+2=9\le 10\) and \(S_2\) weighs \(6+3=9>6\): the solution is not feasible.

3. If \(S_1,S_2\) is feasible for the MKP, the union \(S_1\cup S_2\) weighs at most \(c_1+c_2=16\), so its profit is at most the optimal value of the KP with capacity \(16\). The KP has the optimal solution \(\{2,3,4,5\}\), of weight \(16\) and profit \(40\): \(\mathrm{UB}=40\).

4. The items \(\{2,3,4,5\}\) of the KP solution can be split between the two knapsacks: \(S_1=\{2,3,5\}\) weighs \(10\le 10\) and \(S_2=\{4\}\) weighs \(6\le 6\). Its profit \(40\) attains the dual bound, so it is optimal: \(z(I)=40\). The enumeration of the \(100\) feasible solutions shows that it is the only optimal one.

   

The optimal solution puts \(\{2,3,5\}\) in knapsack \(1\) and \(\{4\}\) in knapsack \(2\), with \(z(I)=40\), equal to the dual bound of the KP with capacity \(c_1+c_2\).

Exercise 2.5: One item per class (MCKP)

We consider the multiple-choice knapsack instance with capacity \(c=16\) and \(n=7\) items, partitioned into the classes \(\mathscr{J}_1=\{1,2\}\), \(\mathscr{J}_2=\{3,4,5\}\), \(\mathscr{J}_3=\{6,7\}\), with the following profits and weights:

\[ \begin{array}{l|ccccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} & {j=7} \\[1ex] \hline {p_j} & {5} & {8} & {14} & {13} & {11} & {12} & {6} \\[1ex] {w_j} & {6} & {9} & {4} & {6} & {7} & {8} & {2} \\ \hline \end{array} \]

Questions

1. Check the feasibility condition \(\sum_h \min_{j\in\mathscr{J}_h} w_j\le c\) of the assumptions.

2. How many candidate solutions are there? Is the choice of the most profitable item of every class feasible?

3. Find the optimal solution by enumeration.

Solution

1. The lightest items of the classes weigh \(6, 4, 2\), and \(6+4+2=12\le 16\): the instance has a feasible solution.

2. A candidate solution takes one item per class: \(2\cdot 3\cdot 2=12\) candidates. The most profitable items are \(2, 3, 6\), of total weight \(9+4+8=21>16\): this choice is not feasible.

3. The candidates are:

   \(S\)	weight	profit	feasible	\(S\)	weight	profit	feasible
   \(\{1,3,6\}\)	\(18\)	\(31\)	no	\(\{2,3,6\}\)	\(21\)	\(34\)	no
   \(\{1,3,7\}\)	\(12\)	\(25\)	yes	\(\{2,3,7\}\)	\(15\)	\(\mathbf{28}\)	yes
   \(\{1,4,6\}\)	\(20\)	\(30\)	no	\(\{2,4,6\}\)	\(23\)	\(33\)	no
   \(\{1,4,7\}\)	\(14\)	\(24\)	yes	\(\{2,4,7\}\)	\(17\)	\(27\)	no
   \(\{1,5,6\}\)	\(21\)	\(28\)	no	\(\{2,5,6\}\)	\(24\)	\(31\)	no
   \(\{1,5,7\}\)	\(15\)	\(22\)	yes	\(\{2,5,7\}\)	\(18\)	\(25\)	no

   Only \(4\) candidates are feasible, and the best one is \(\tilde S=\{2,3,7\}\), of weight \(15\), with \(z(I)=28\); it is the only optimal solution.

The optimal solution takes items \(2, 3, 7\), one per class, with \(z(I)=28\): the most profitable item of every class is not a feasible choice.

Exercise 2.6: A greedy choice that is not optimal (KP)

A fund has a budget of \(c=14\) and \(n=5\) candidate projects, the items \(\mathscr{I}=\{1,\dots,5\}\) of a knapsack instance, with the following profits and costs (weights):

\[ \begin{array}{l|ccccc} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\[1ex] \hline {p_j} & {14} & {9} & {15} & {13} & {11} \\[1ex] {w_j} & {7} & {2} & {9} & {6} & {8} \\ \hline \end{array} \]

Questions

1. Write the instance as a combinatorial optimization problem: ground set, feasible solutions and objective function. How many candidate solutions are there?

2. List the feasible subsets, with weight and profit, and find the optimal solution by brute force.

3. Apply the greedy algorithm by efficiency: sort the items by non-increasing efficiency \(p_j/w_j\) (ties by the smallest index) and insert each item that fits. Is the greedy solution optimal?

4. Compute the dual bound of the continuous relaxation, in which the items can be taken fractionally, and round it. What are the relative gaps of the greedy solution with respect to this bound and with respect to \(z(I)\)?

Solution

1. The ground set is \(\mathscr{U}=\mathscr{I}=\{1,2,3,4,5\}\). A subset \(S\subseteq\mathscr{U}\) is feasible if \(\sum_{j\in S} w_j\le 14\), and the objective is \(f(S)=\sum_{j\in S} p_j\), to be maximized. The candidate solutions are the \(2^5=32\) subsets.

2. The three lightest items weigh \(2+6+7=15>14\), so a feasible subset has at most \(2\) items. The \(12\) feasible subsets are:

   \(S\)	weight	profit	\(S\)	weight	profit
   \(\emptyset\)	\(0\)	\(0\)	\(\{1,2\}\)	\(9\)	\(23\)
   \(\{1\}\)	\(7\)	\(14\)	\(\{1,4\}\)	\(13\)	\(\mathbf{27}\)
   \(\{2\}\)	\(2\)	\(9\)	\(\{2,3\}\)	\(11\)	\(24\)
   \(\{3\}\)	\(9\)	\(15\)	\(\{2,4\}\)	\(8\)	\(22\)
   \(\{4\}\)	\(6\)	\(13\)	\(\{2,5\}\)	\(10\)	\(20\)
   \(\{5\}\)	\(8\)	\(11\)	\(\{4,5\}\)	\(14\)	\(24\)

   The optimal solution is \(\tilde S=\{1,4\}\), of weight \(13\), with \(z(I)=27\); it is the only subset with this profit.

3. The efficiencies are

   \[ \frac{p_1}{w_1}=\frac{14}{7}=2,\quad \frac{p_2}{w_2}=\frac{9}{2},\quad \frac{p_3}{w_3}=\frac{15}{9}=\frac{5}{3},\quad \frac{p_4}{w_4}=\frac{13}{6},\quad \frac{p_5}{w_5}=\frac{11}{8}, \]

   so the order is \(2,4,1,3,5\). The greedy algorithm examines the items in this order:

   • item \(2\) fits (weight \(2\)): residual capacity \(12\);

   • item \(4\) fits (weight \(6\)): residual capacity \(6\);

   • item \(1\) does not fit (weight \(7 > 6\));

   • item \(3\) does not fit (weight \(9 > 6\));

   • item \(5\) does not fit (weight \(8 > 6\));

   It returns \(\bar S=\{2,4\}\), of profit \(22\): a primal bound \(\mathrm{LB}=22\). It is not optimal, since \(z(I)=27\). The two efficient items fill \(8\) units of the budget, and the residual capacity \(6\) is too small for any other item; the optimal solution gives up item \(2\), the most efficient one, and uses \(13\) of the \(14\) units of the budget with items \(1\) and \(4\).

4. In the continuous relaxation the items are taken in the same order: items \(2, 4\) fill \(8\) units, and the fraction \(\frac{6}{7}\) of item \(1\) fills the residual capacity \(6\):

   \[ \mathrm{UB}=9+13+\frac{6}{7}\cdot 14=34. \]

   The bound is an integer, no rounding is needed. With respect to the bound, the relative gap of the greedy solution is \(\frac{34-22}{22}=\frac{6}{11}\approx 54.5\%\); with respect to the optimum it is \(\frac{27-22}{22}=\frac{5}{22}\approx 22.7\%\). Without the enumeration, the bound alone cannot certify the optimum.

The greedy choice by efficiency gives profit \(22\), while the optimum, found by brute force over the \(12\) feasible subsets, is \(z(I)=27\) with \(\tilde S=\{1,4\}\): \(22\le z(I)=27\le 34\).