Multiple-choice knapsack problem (MCKP)

Catalogue of combinatorial problems · Knapsack problems · Catalogue (PDF)

Definition 1: Multiple-choice knapsack problem

Given:

1. a knapsack of capacity \(c \in \Z_{\ge 1}\),

2. a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items,

3. the set of items is partitioned into \(q \in \Z_{\ge 2}\) classes,

4. for each class \(h \in \{1,2,\dots,q\}\), the subset \(\mathscr{J}_h \subseteq \mathscr{I}\) contains the items of that class,

5. 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.

Assumptions

• We make the following assumptions:

  1. 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\}. \]

  2. 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. \]

What the course does on this problem

Technique	Where
Definition	Ch. 2 «Knapsack problems»
Formulations	Ch. 9 «Formulations of knapsack problems»
Dynamic programming	Ch. 16 «Principles of dynamic programming»; Ch. 21 «DP for the multiple-choice knapsack problem»
Exercises	Exercise 2.5; Exercise 9.11; Exercise 16.5; Ch. 21 (5 exercises)