Multiple knapsack problem (MKP)

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

Definition 1: Multiple knapsack problem

Given:

1. \(m \in \Z_{\ge 1}\) knapsacks,

2. for each knapsack \(k \in \underbrace{\{1,2,\dots,m\}}_{=\mathscr{K}}\), a capacity \(c_k \in \Z_{\ge 1}\),

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

4. 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 Knapsack Problem (MKP) asks to decide which items to insert into each knapsack, so that in every knapsack the total weight of the assigned items does not exceed its capacity, and the total profit of the selected items is maximized.

Assumptions

• We make the following assumptions:

  1. The set of all items does not fit in the knapsacks altogether (otherwise, selecting all items is feasible and optimal). Formally,

     \[ \sum_{j\in \mathscr{I}} w_j \;>\; \sum_{k\in \mathscr{K}} c_k . \]

  2. Each item individually fits in (at least) one knapsack (otherwise, it can never be selected). Formally,

     \[ \forall\, j\in \mathscr{I}\quad \exists\, k\in \mathscr{K}\ \text{such that}\ w_j \le c_k . \]

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. 24 «DP for the multiple knapsack problem»
Exercises	Exercise 2.4; Exercise 9.10; Ch. 24 (5 exercises)