2.6 The multidimensional 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.6: Multidimensional Knapsack Problem
Given:
-
a \(k\)-dimensional knapsack,
-
for each dimension \(d \in \underbrace{\{1,2,\dots,k\}}_{=\mathscr{D}}\), a capacity \(c_d \in \Z_{\ge 1}\),
-
a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items,
-
for each item \(j \in \mathscr{I}\), a profit \(p_j \in \Z_{\ge 1}\),
-
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.
-
An MDKP instance is specified by:
-
two integer numbers:
-
the number of items \(n \in \Z_{\ge 1}\),
-
the number of dimensions \(k \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 \(k\):
- \(\vet{c} \in \Z_{\ge 1}^k\), containing the knapsack capacities for each dimension,
-
one matrix of integer numbers with \(k\) rows and \(n\) columns:
- \(\vet{W} \in \Z_{\ge 1}^{k \times n}\), containing the weights of the items for each dimension.
-
-
An MDKP feasible solution is a subset of items
\[ S \subseteq \mathscr{I} \]such that the capacity constraints are satisfied in every dimension, namely
\[ \sum_{j\in S} w_{dj} \le c_d \qquad \forall\, d\in \mathscr{D}. \]Accordingly, the MDKP can be equivalently stated as the problem of selecting a subset of items whose total weight respects the knapsack capacities in every dimension, and whose total profit is maximized.
Given an MDKP instance, the MDKP can be formally stated as:
\[\begin{equation*} \label{MDKP} \tilde{S}\in \argmax_{S \subseteq \mathscr{I}} \left\{~~ \sum_{j \in S} p_j \;\;:\;\; \sum_{j\in S} w_{dj} \le c_d \ \ \forall\, d\in \mathscr{D} ~~\right\}. \tag{2.8} \end{equation*}\]
Example 2.5: MDKP instance
We consider a \(2\)-dimensional knapsack (\(k=2\)) with capacities \(c_1 = 10\) and \(c_2 = 12\), and a set \(\mathscr{I} = \{1,2,3,4\}\) of \(4\) items (\(n = 4\)), with the following profits and weights:
| Items | \(j = 1\) | \(j = 2\) | \(j = 3\) | \(j = 4\) | |
|---|---|---|---|---|---|
| Profits | \(p_j\) | \(6\) | \(7\) | \(5\) | \(9\) |
| Weights (dim. \(1\)) | \(w_{1j}\) | \(4\) | \(5\) | \(3\) | \(7\) |
| Weights (dim. \(2\)) | \(w_{2j}\) | \(6\) | \(4\) | \(5\) | \(3\) |
The drawing has one box per dimension, of length \(c_1=10\) and \(c_2=12\): a selected item occupies a block of length \(w_{1j}\) in the first box and one of length \(w_{2j}\) in the second. The optimal solution \(\{3,4\}\) fills the first dimension and uses \(8\) units of the second, with profit \(5+9=14\).
2.6.1 Assumptions¶
-
We make the following assumptions:
-
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 . \] -
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}. \]
-