List of knapsack problems

From Wikipedia, the free encyclopedia

The knapsack problem is one of the most studied problems in combinatorial optimization, with many real-life applications. For this reason, many special cases and generalisations have been examined.

Common to all versions are a set of n items, with each item $1 \leq j \leq n$ having an associated profit p_j and weight w_j. The objective is to pick some of the items, with maximal total profit, while obeying that the maximum total weight of the chosen items must not exceed W. Generally, these coefficients are scaled to become integers, and they are almost always assumed to be positive.

The knapsack problem in its most basic form:

maximize $\sum_{j=1}^n p_j x_j$
subject to	$\sum_{j=1}^n w_j x_j \leq W,$
	$x_j \in \{0,1\}$	$\forall j \in \{1,\ldots, n\}$

[edit] Direct generalizations

If each item can be chosen multiple times, we get the bounded knapsack problem. Notice that because the weight of each item is at least 1, we can never choose an item more than W times.

maximize $\sum_{j=1}^n p_j x_j$
subject to	$\sum_{j=1}^n w_j x_j \leq W,$
	$x_j \in \{0,1,\ldots , W\},$	$\forall j \in \{1,\ldots, n\}$

If the items are subdivided into k classes denoted $N i$ , and exactly one item must be taken from each class, we get the multiple-choice knapsack problem:

maximize $\sum_{i=1}^k\sum_{j\in N_i} p_{ij} x_{ij}$
subject to	$\sum_{i=1}^k\sum_{j\in N_i} w_{ij} x_{ij} \leq W,$
	$\sum_{j \in N_i}x_{ij} = 1,$	for all $1 \leq i \leq k$
	$x_{ij} \in \{0,1\}$	for all $1 \leq i \leq k$ and all $j \in N_i$

If for each item the profits and weights are identical, we get the subset sum problem (often the corresponding decision problem is given instead):

maximize $\sum_{j=1}^n p_j x_j$
subject to	$\sum_{j=1}^n p_j x_j \leq W,$
	$x_j \in \{0,1\}$

If we have n items and m knapsacks with capacities $W i$ , we get the multiple knapsack problem:

maximize $\sum_{i=1}^m\sum_{j=1}^n p_j x_{ij}$
subject to	$\sum_{j=1}^n w_j x_{ij} \leq W_i,$	for all $1 \leq i \leq m$
	$\sum_{i=1}^m x_{ij} = 1,$	for all $1 \leq j \leq n$
	$x_{ij} \in \{0,1\}$	for all $1 \leq j \leq n$ and all $1 \leq i \leq m$

If in the multiple knapsack problem the weights are not the same in every container and we are allowed to choose each item multiple times, we get the multiple constrained knapsack problem: Notice that this is a general integer problem, with positive coefficients.

maximize $\sum_{j=1}^n p_j x_j$
subject to	$\sum_{j=1}^n w_{ij} x_j \leq W_i,$	for all $1 \leq i \leq m$
	$x_j \geq 0$ , $x j$ integer	for all $1\leq j \leq n$

Quadratic knapsack problem

maximize $\sum_{j=1}^n p_j x_j+\sum_{i=1}^{n-1}\sum_{j=i+1}^n p_{ij} x_i x_j$
subject to	$\sum_{j=1}^n w_j x_j \leq W,$
	$x_j \in \{0,1\}$	for all $1 \leq j \leq n$

[edit] Knapsack-like problems

If all the profits are 1, we can try to minimize the number of items which exactly fill the knapsack. This is the change-making problem:

minimize $\sum_{j=1}^n x_j$
subject to	$\sum_{j=1}^n w_j x_j = W,$
	$x_j \in \{0,1\},$	$\forall j \in \{1,\ldots,n\}$

If we have a number of containers (of the same size), and we wish to pack all n items in as few containers as possible, we get the bin packing problem, which is modelled by having indicator variables $y_i=1 \Leftrightarrow$ container i is being used:

minimize $\sum_{i=1}^n y_i$
subject to	$\sum_{j=1}^n w_j x_{ij} \leq Wy_i,$	$\forall i \in \{1,\ldots,n\}$
	$\sum_{i=1}^n x_{ij} \leq 1$	$\forall j \in \{1,\ldots,n\}$
	$y_i \in \{0,1\}$	$\forall i \in \{1,\ldots,n\}$
	$x_{ij} \in \{0,1\}$	$\forall i \in \{1,\ldots,n\} \wedge \forall j \in \{1,\ldots,n\}$

The cutting stock problem is identical to the bin packing problem, but since practical instances usually have far fewer types of items, another formulation is often used. Item j is needed B_j times, each "pattern" of items which fit into a single knapsack have a variable, x_i (there are m patterns), and pattern i uses item j b_ij times:

minimize $\sum_{i=1}^m x_i$
subject to	$\sum_{i=1}^m b_{ij} x_i \leq B_j,$	for all $1 \leq j \leq n$
	$x_i \in \{0,1,\ldots ,n\}$	for all $1\leq i \leq m$

If, to the multiple choice knapsack problem, we add the constraint that each subset is of size n and remove the restriction on total weight, we get the assignment problem, which is also the problem of finding a maximal bipartite matching:

minimize $\sum_{i=1}^k\sum_{j=1}^n p_{ij} x_{ij}$
subject to	$\sum_{i=1}^n x_{ij} = 1,$	for all $1 \leq j \leq n$
	$\sum_{j=1}^n x_{ij} = 1,$	for all $1 \leq i \leq n$
	$x_{ij} \in \{0,1\}$	for all $1 \leq i \leq k$ and all $j \in N_i$