2.8 The multiple-choice knapsack problem¶
Part 1 · Combinatorial optimization problems · Chapter 2 · Chapter 2: Knapsack problems · Lecture notes, volume 1 (PDF) · Slides · Exercises: Knapsack problems · App: Brute force on the 0/1 knapsack problem
Definition 2.8: Multiple-Choice Knapsack Problem
Given:
-
a knapsack of capacity \(c \in \Z_{\ge 1}\),
-
a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items,
-
the set of items is partitioned into \(q \in \Z_{\ge 2}\) classes,
-
for each class \(h \in \{1,2,\dots,q\}\), the subset \(\mathscr{J}_h \subseteq \mathscr{I}\) contains the items of that class,
-
for each item \(j \in \mathscr{I}\), a profit \(p_j \in \Z_{\ge 1}\) and a weight \(w_j \in \Z_{\ge 1}\),
the Multiple-Choice Knapsack Problem (MCKP) asks to decide which items to insert into the knapsack, so that exactly one item is selected from each class, the total weight of the selected items does not exceed the knapsack capacity, and the total profit of the selected items is maximized.
-
An MCKP instance is specified by:
-
two integer numbers:
-
the number of items \(n \in \Z_{\ge 1}\),
-
the knapsack capacity \(c \in \Z_{\ge 1}\),
-
-
one vector of integer numbers of length \(n\):
- \(\vet{p} \in \Z_{\ge 1}^n\), containing the item profits,
-
one vector of integer numbers of length \(n\):
- \(\vet{w} \in \Z_{\ge 1}^n\), containing the item weights,
-
one integer number:
- the number of classes \(q \in \Z_{\ge 2}\),
-
one family of subsets:
- \(\{ \mathscr{J}_1, \mathscr{J}_2, \dots, \mathscr{J}_q \}\), a partition of \(\mathscr{I}\) into \(q\) classes, where \(\mathscr{J}_h \subseteq \mathscr{I}\) is the set of items belonging to class \(h\).
-
-
An MCKP feasible solution is a subset of items
\[ S \subseteq \mathscr{I} \]such that:
-
(i) exactly one item is selected from each class, namely
\[ |S \cap \mathscr{J}_h| = 1 \qquad \text{for all } h\in\{1,2,\dots,q\}; \] -
(ii) the total weight of the selected items does not exceed the knapsack capacity, namely
\[ \sum_{j\in S} w_j \le c. \]
Accordingly, the MCKP can be equivalently stated as the problem of selecting exactly one item from each class such that the knapsack capacity is respected and the total profit is maximized.
Given an MCKP instance, the MCKP can be formally stated as:
\[\begin{equation*} \label{MCKP} \tilde{S}\in \argmax_{S \subseteq \mathscr{I}} \left\{ ~~ \sum_{j \in S} p_j \;\;:\;\; \sum_{j \in S} w_j \le c,\ \ |S \cap \mathscr{J}_h| = 1 \ \ \forall\, h\in\{1,2,\dots,q\} ~~\right\}. \tag{2.10} \end{equation*}\] -
Example 2.7: MCKP instance
We consider a knapsack of capacity \(c = 15\) and a set \(\mathscr{I} = \{1,2,3,4,5,6\}\) of \(6\) items (\(n = 6\)). The items are partitioned into \(q = 3\) classes: \(\mathscr{J}_1 = \{1,2\}\), \(\mathscr{J}_2 = \{3,4\}\), \(\mathscr{J}_3 = \{5,6\}\). The profits and weights are given as follows:
| Items | \(j = 1\) | \(j = 2\) | \(j = 3\) | \(j = 4\) | \(j = 5\) | \(j = 6\) | |
|---|---|---|---|---|---|---|---|
| Profits | \(p_j\) | \(6\) | \(8\) | \(5\) | \(7\) | \(4\) | \(9\) |
| Weights | \(w_j\) | \(4\) | \(6\) | \(5\) | \(8\) | \(3\) | \(7\) |
In the drawing every class is a coloured group, and the item chosen in each class is drawn solid, the other one dashed. An optimal solution, \(\{1,4,5\}\), fills the knapsack, with weight \(4+8+3=15\) and profit \(6+7+4=17\).
2.8.1 Assumptions¶
-
We make the following assumptions:
-
Each class contains at least one item (otherwise, selecting exactly one item from each class is impossible). Formally:
\[ \mathscr{J}_h \neq \emptyset \qquad \forall\, h\in\{1,\dots,q\}. \] -
The instance is feasible, i.e., there exists at least one choice of exactly one item per class that fits in the knapsack. A necessary and sufficient (and easy-to-check) condition is:
\[ \sum_{h=1}^{q}\ \min_{j\in \mathscr{J}_h} w_j \;\le\; c. \]
-