2.4 The bounded 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.4: Bounded Knapsack Problem
Given:
-
a knapsack of capacity \(c \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}\), a weight \(w_j \in \Z_{\ge 1}\), and a number of available copies \(b_j \in \Z_{\ge 1}\),
the Bounded Knapsack Problem (BKP) asks to decide how many copies of each item to insert into the knapsack, so that the total weight of all selected item copies does not exceed the knapsack capacity, each item is taken no more than its available copies, and the total profit of all selected item copies is maximized.
-
A BKP instance is specified by:
-
two integer numbers:
-
the number of items \(n \in \Z_{\ge 1}\),
-
the knapsack capacity \(c \in \Z_{\ge 1}\),
-
-
three vectors of integer numbers of length \(n\):
-
\(\vet{p} \in \Z_{\ge 1}^n\), containing the item profits,
-
\(\vet{w} \in \Z_{\ge 1}^n\), containing the item weights,
-
\(\vet{b} \in \Z_{\ge 1}^n\), containing the number of available copies of each item.
-
-
-
Given a BKP instance, we define the extended set of items as
\[\begin{equation*} \label{ExtSet} \hat{\mathscr{I}} = \big\{\, (j,k) : j \in \mathscr{I},~ k \in \{1,2,\dots,b_j\} \,\big\}, \tag{2.3} \end{equation*}\]where each pair \((j,k)\) represents the \(k\)-th available copy of item \(j\). The cardinality of the extended set of items is
\[ |\hat{\mathscr{I}}| = \sum_{j \in \mathscr{I}} b_j. \] -
A BKP feasible solution is a subset of items
\[ S \subseteq \hat{\mathscr{I}} \]such that the total weight of the selected items does not exceed the knapsack capacity, namely
\[ \sum_{(j,k)\in S} w_j \le c . \]Accordingly, the BKP can be equivalently stated as the problem of selecting a subset of the extended set of items whose total weight respects the knapsack capacity, and whose total profit is maximized.
Given a BKP instance, the BKP can be formally stated as:
\[\begin{equation*} \label{BKP} \tilde{S}\in \arg\max_{S \subseteq \hat{\mathscr{I}} } \left\{~~ \sum_{(j,k) \in S} p_j \;:\; \sum_{(j,k) \in S} w_j \le c ~~\right\}. \tag{2.4} \end{equation*}\]
Example 2.3: BKP instance
We consider a knapsack of capacity \(c = 9\) and a set \(\mathscr{I} = \{1,2,3,4,5,6\}\) of \(6\) items (\(n = 6\)), with the following profits, weights, and available copies:
| Items | \(j = 1\) | \(j = 2\) | \(j = 3\) | \(j = 4\) | \(j = 5\) | \(j = 6\) | |
|---|---|---|---|---|---|---|---|
| Profits | \(p_j\) | \(6\) | \(5\) | \(8\) | \(9\) | \(6\) | \(7\) |
| Weights | \(w_j\) | \(2\) | \(3\) | \(6\) | \(7\) | \(5\) | \(9\) |
| Available copies | \(b_j\) | \(2\) | \(2\) | \(1\) | \(1\) | \(1\) | \(1\) |
The extended set of items is:
Each copy \((j,k)\) has profit \(p_j\) and weight \(w_j\).
| Copy label | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \((j,k)\) | \((1,1)\) | \((1,2)\) | \((2,1)\) | \((2,2)\) | \((3,1)\) | \((4,1)\) | \((5,1)\) | \((6,1)\) |
| Profit \(p_j\) | \(6\) | \(6\) | \(5\) | \(5\) | \(8\) | \(9\) | \(6\) | \(7\) |
| Weight \(w_j\) | \(2\) | \(2\) | \(3\) | \(3\) | \(6\) | \(7\) | \(5\) | \(9\) |
The drawing shows an optimal solution: the two copies of item \(1\) and the copy of item \(5\), with weight \(2+2+5=9\) and profit \(6+6+6=18\).
2.4.1 Assumptions¶
-
We make the following assumptions:
-
The total weight of all available copies of all items exceeds the knapsack capacity (otherwise, all copies could be selected). Formally:
\[ \sum_{j \in \mathscr{I}} b_j \, w_j > c \] -
Each item individually fits into the knapsack (otherwise, it cannot be selected). Formally:
\[ w_j \le c, \qquad \forall j \in \mathscr{I} \] -
The total weight of all available copies of any single item does not exceed the knapsack capacity (otherwise, that item could never be taken in the maximum allowed number of copies). Formally:
\[ b_j \, w_j \le c, \qquad \forall j \in \mathscr{I} \]
-