Multidimensional knapsack problem (MDKP)

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

Definition 1: Multidimensional knapsack problem

Given:

1. a \(k\)-dimensional knapsack,

2. for each dimension \(d \in \underbrace{\{1,2,\dots,k\}}_{=\mathscr{D}}\), a capacity \(c_d \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}\),

5. for each dimension \(d \in \mathscr{D}\) and each item \(j \in \mathscr{I}\), a weight \(w_{dj} \in \Z_{\ge 1}\),

the Multidimensional Knapsack Problem (MDKP) asks to decide which items to insert into the knapsack, so that for every dimension the total weight of the selected items does not exceed the corresponding 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 knapsack (otherwise, selecting all items is feasible and optimal). Formally,

     \[ \exists\, d\in \mathscr{D} \ \text{such that}\ \sum_{j\in \mathscr{I}} w_{dj} \;>\; c_d . \]

  2. Each item individually fits in the knapsack in every dimension (otherwise, it can never be selected). Formally,

     \[ w_{dj} \le c_d, \qquad \forall\, d\in \mathscr{D},\ \forall\, j\in \mathscr{I}. \]

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. 22 «DP for the multidimensional knapsack problem»
Exercises	Exercise 9.9; Ch. 22 (5 exercises)