The 0/1 knapsack problem (KP)¶
Definition 1: The 0/1 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}\) and a weight \(w_j \in \Z_{\ge 1}\),
the 0/1 Knapsack Problem (KP) asks to decide which items to insert into the knapsack, so that 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:
-
The total weight of all items exceeds the knapsack capacity (otherwise, all items could be selected). Formally:
\[ \sum_{j \in \mathscr{I}} w_j > c \] -
Each item individually fits into the knapsack (otherwise, it cannot be selected). Formally:
\[ w_j \le c,~~~~ \forall j \in \mathscr{I} \]
-
What the course does on this problem¶
Properties¶
-
Weakly NP-hard: dynamic programming solves it in \(\Theta(nc)\) steps, a pseudo-polynomial time (Ch. 1).
-
Cardinality bound: if at most \(\bar k\) items fit, \(z(I)\) is at most the sum of the \(\bar k\) largest profits (Ch. 2).
-
Sorting by efficiency is not enough: on the instance of Ch. 2 it gives profit \(11\), while the optimum is \(15\) (Ch. 2).
Formulations¶
-
The model \(\ILP_{\KP}\) has one binary variable per item and one capacity constraint (Ch. 9).
-
The relaxation \(\LP_{\KP}\) is solved by sorting the items by efficiency: the items before the split item \(s\) are taken, \(s\) only in part (Ch. 9).
-
\(z(\LP_{\KP}) \le 2\, z(\ILP_{\KP})\), and the ratio \(2\) is approached (Ch. 9).
-
Rounding down \(z(\LP_{\KP})\) gives the Dantzig bound \(\UB_{\mathrm{D}}\); the Martello–Toth bound \(\UB_{\mathrm{MT}}\) treats the split item out and in (Ch. 9).
Dynamic programming¶
-
The recurrence \(v(j,k)\) over items and capacities takes \(\Theta(nc)\) steps (Ch. 17).
-
The lists of non-dominated states keep only the reachable states, at most \(\min\{2^j, c+1\}\) per stage (Ch. 17).
-
The DP by profits takes \(\Theta(nP)\) steps; it is the core of the FPTAS (Ch. 17).
-
The UKP and the BKP have their own recurrences (Ch. 18, Ch. 19).
-
So do the SSP, the MCKP and the KPS, in \(\Theta(nc)\) steps; for the MDKP and the MKP the table grows exponentially with the number of capacities (Ch. 20, Ch. 21, Ch. 22, Ch. 23, Ch. 24).
Heuristics¶
-
Greedy by profit, by weight and by efficiency: on the four-item instance of Ch. 29 (optimum \(17\)) they give \(17\), \(10\) and \(16\) (Ch. 30).
-
Flip and swap local search: first and best improvement reach \(17\) along different paths (Ch. 31).
-
A penalty on the excess weight lets the search cross infeasible solutions; with \(\alpha>\max_j p_j\) its local optima are feasible (Ch. 31).
-
Simulated annealing, GRASP, genetic and memetic algorithms; on KP20 the memetic algorithm reaches the optimum \(521\) in every run (Ch. 32).
MIP heuristics¶
-
Rounding down the LP solution is always feasible, since the model has a single packing constraint (Ch. 33).
-
On the instance of Ch. 29 fractional diving ends at \(16\) and RINS fails, while local branching and proximity search reach and prove the optimum \(17\) (Ch. 33).
Approximation¶
-
The greedy algorithm has no constant guarantee; Ext-Greedy is a \(2\)-approximation, and the bound is tight (Ch. 35).
-
\(H^{\ell}\) guarantees \(\frac{\ell+2}{\ell+1}\) in \(O(n^{\ell+1})\) time, which gives a PTAS (Ch. 35).
-
The Basic-FPTAS scales the profits and guarantees \(\frac{1}{1-\varepsilon}\) in \(O(n^2/\varepsilon)\) time (Ch. 35).
-
No polynomial algorithm has a fixed absolute guarantee, unless it solves the KP exactly (Ch. 35).
Ad hoc algorithms¶
- The LP of a node is solved by the Dantzig formulas, without the simplex algorithm, and has one fractional variable: the split item, on which it branches (Ch. 41).