0-1 knapsack problem

The 0-1 quadratic knapsack problem (QKP) is an extension of knapsack problem that allows for quadratic terms in the objective function with a restriction on the number of copies of each kind of item: Given a set of items, each with a weight, a value, and an extra profit that can be earned if both items are selected, determine which item to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit.

The 0-1 quadratic knapsack problem is a variation of knapsack problems, combing the features of unbounded knapsack problem, 0-1 knapsack problem and quadratic knapsack problem.

Definition

Specifically, the 0-1 quadratic knapsack problem has the following form:

maximize $\{\sum _{i=1}^{n}p_{i}x_{i}+\sum _{i=1}^{n}\sum _{j=1,i\neq j}^{n}P_{ij}x_{i}x_{j}:x\in X,x$ binary $\}$

subject to $X\equiv \{x\in \mathbb {R} ^{n}:\sum _{i=1}^{n}w_{i}x_{i}\leq W;0\leq x_{i}\leq 1$ for $i=1,\cdots ,n\}$.

While the binary variable x_i represents whether item i is included in the knapsack, p_i is the profit earned by selecting item i and P_ii is the profit achieved if both item i and j are added.

Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack's capacity.

Computational Complexity

In general, the decision version of the knapsack problem (Can a value of at least V be achieved under a restriction of a certain capacity W?) is NP-complete. Thus, a given solution can be verified to in polynomial time while no algorithm can identify a solution efficiently.

The optimization knapsack problem is NP-hard and there is no know algorithm that can solve the problem in polynomial time.

As a particular variation of the knapsack problem, the 0-1 quadratic knapsack problem is also NP-hard, thus no efficient algorithm presenting in the literature.

While no available efficient algorithm in the literature. there is a pseudo-polynomial based on dynamic programming and other heuristic algorithms that can always generate “good” solutions.

Solving

While the knapsack problem is one of the most commonly solved OR problems, there are limited efficient algorithms that can solve 0-1 quadratic knapsack problems. Available algorithms include but are not limited to brute forth, linearization, and convex reformulation. Just like other NP-hard problems, it is usually enough to find a workable solution which is not necessary to be optimal. Heuristic algorithms based on greedy algorithm, dynamic programming can give a relatively “good” solution to the 0-1 QKP efficiently.

Brute forth

The brute forth algorithm to solve this problem is to identify all possible subsets of the items without exceeding the capacity and select the one with the optimal value. The pseudo-code is provided as follows:

// Input:
// Profits (stored in array p)
// Quadratic profits (stored in matrix P)
// Weights (stored in array w)
// Number of items (n)
// Knapsack capacity (W)

int max =0
for all subset S do
	int value, weight = 0
 	for i from 0 to S.size-1 do:
		value = value +p[i]
		weight = weight +w[i]
			for j from i+1 to S.size-1 do: 
				value = value + P[i][j]
	if weight <= W then:
		if value > max then:	
			max = value

Given n items, there will be at most $2^{n}$ subsets and for each legal candidate set, the running time of computing the values earned is $O(n^{2})$. Thus, the efficiency class of brute forth algorithm is $O(2^{n}n^{2})=O(2^{n})$, being exponential.

Linearization

Problems of such form are difficult to solve directly using standard solvers and thus people try to reformulate it as a linear program using auxiliary variables and constraints so that the problem can be readily solved using commercial packages. Two well-known linearization approaches for the 0-1 QKP are the standard linearization and Glover’s linearization.

Standard Linearization

The first one is the standard linearization strategy, as shown below:

LP1: maximize

$\sum _{i=1}^{n}p_{i}x_{i}+\sum _{i=1}^{n}(\sum _{j=1,i\neq j}^{n}(P_{ij}x_{i}x_{j}+P_{ji})z_{ij})$.

subject to

$z_{ij}\leq x_{i}$ for all $(i,j),i<j$

$z_{ij}\leq x_{i}$ for all $(i,j),i<j$

$z_{ij}\leq x_{j}$ for all $(i,j),i<j$

$x_{i}+x_{j}-1\leq z_{ij}$ for all $(i,j),i<j$

$z_{ij}\geq 0$ for all $(i,j),i<j$

$x\in X,x$ binary

In the formulation LP1, we have replaced the x_ix_j term with a continuous variable z_ij. After reformulate QKP into knapsack problem, we can always submit it to the standard solvers, which can provide an optimal solution.

Glover'Linearization

The second reformulation, which is more concise, is called Glover’s linearization. The Glover formulation is shown below, where L_i and U_i are lower and upper bounds on $\sum _{j=1}^{n}P_{ij}x_{i}x_{j}$, respectively:

LP2: maximize

$\sum _{i=1}^{n}p_{i}x_{i}+\sum _{i=1}^{n}z_{ij}$

subject to

$L_{i}\leq z_{i}\leq U_{i}$ for all $i=1,\cdots ,n$

$\sum _{j=1}^{n}P_{ij}x_{i}-U_{i}(1-x_{i})\leq z_{i}\leq \sum _{j=1}^{n}P_{ij}x_{i}-L_{i}(1-x_{i})$ for all $i=1,\cdots ,n$

$x\in X,x$ binary

In the formulation LP2, we have replaced the expression ($\sum _{j=1}^{n}P_{ij}x_{j}$) with a continuous variable z_i. Similarly, we can use standard solvers to solve the linearization problem.

Convex quadratic reformulation

Note that nonlinear programs are hard to solve due to the possibility of being stuck at a local maximum. However, when the program is convex, any local maximum is the global maximum. Thus by rewriting the objective function into an equivalent convex function, we can reformulate the program to be convex, which can be solved using optimization packages.

The objective function can be written as $c^{T}x+x^{t}Cx$ using linear algebra notation. We need to make P a positive semi-definite matrix in order to reformulate a convex function. In this case, we modify the objective function to be $p^{T}x+x^{t}Px+\sum _{i=1}^{n}(\sum _{j=1,j\neq i}^{n}|P_{ij}|)(x_{i}^{2}-x_{i})$ by applying results from linear algebra, where P is made diagonally dominant and thus a positive semi-definite. This reformulation can be solved using a standard commercial mixed-integer quadratic package.

Quadknap

Quadknap is a branch-and-bound algorithm raised by , where upper bounds are computed by considering a Lagrangian relaxation which releases the integer requirement. Suboptimal Lagrangian multipliers are derived by using sub-gradient optimization and provide a convenient reformulation of the problem.

Dynamic programming heuristic

Dynamic programming approaches can yield a highly effective heuristic solution, which can serve as a lower bound to the optimal objectives. While it runs in pseudo-polynomial time, it has a large memory requirement.

Dynamic programming algorithm

For simplicity, assume all weights are non-negative. The objective is to maximize total value subject to the constraint: that the total weight is less than or equal to W. Then for each $w\leq W$, define $f(m,w)$ to be the value of the most profitable packing of the first m items found with a total weight of w. That is, let $f(m,w)=max\{\sum _{i=1}^{m}p_{i}x_{i}+\sum _{i=1}^{m}\sum _{j=1,i\neq j}^{m}P_{ij}x_{i}x_{j}:\sum _{i=1}^{m}w_{i}=w,1\leq i\leq m\}$

Then, $f(m,w)$ is the solution to the problem. Note that by dynamic programming, the solution to a problem arises from the solution to its smaller sub-problems. In this particular case, start with the first item and try to find a better packing by considering adding items with an expected weight of 𝑤. If the weight of the item to be added exceeds 𝑤, then $f(m,w)$ is the same with $f(m-1,w)$. Given that the item has a smaller weight compared with the desired weight, $f(m,w)$ is either the same as $f(m-1,w)$ if adding makes no contribution, or the same as the solution for a knapsack with smaller capacity, specifically one with the capacity reduced by the weight of that chosen item, plus the value of one correct item, i.e. $f(m-1,w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}$. To conclude, we have that $f(m,w)=$

max $f(m-1,w),f(m-1,w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}$ if $w_{m}\leq w,$

$f(m-1,w)$ otherwise.

Also, define $S(m,w)$ to be the corresponding set of items in the most profitable packing. This helps keep track of the currently best packing. The pseudo code is as follows:

Initialize f(m,w) to -infinity, S(m,w)=\emptyset for all m,w
Set f(0,0) to 0
for m from 1 to n do:
 	for w from 0 to W do:
		if f(m-1,w) > f(m,w) then:
			f(m,w) = f(m-1,w)
                        S(m,w) = S(m-1,w)
		if w+w[m] < W then:
                        let p be the profit of S(m-1,w)+{m}
	                if p > f(m,w+w[m]) then:
		                f(m,w+w[m]) = p
			        S(m,w+w[m]) = S(m-1,w)+{m}

Note on efficiency class: Clearly the running time of this algorithm is $O(Wn^{2})$, based on the nested loop and the computation of the profit of new packing. This does not contradict the fact the QKP is NP-hard since W is not polynomial in the length of the input.

This algorithm requires $O(Wn^{2})$ space for storing $S(m,w)$ for all m,w, which may not be able to handle large-size problems. In fact, this can be easily improved by dropping the index m from $f(m,w)$ since all the computations depend only on the results from the preceding stage.

Revised dynamic programming algorithm

Redefine $f(w)$ to be the current value of the most profitable packing found by the heuristic. That is, $f(w)=max\{\sum _{i=1}^{m}p_{i}x_{i}+\sum _{i=1}^{m}\sum _{j=1,i\neq j}^{m}P_{ij}x_{i}x_{j}:\sum _{i=1}^{m}w_{i}=w,m\leq n\}$ Accordingly, by dynamic programming we have that $f(w)=$

max $f(w),f(w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}$ if $w_{m}\leq w,$

$f(w)$ otherwise.

Also instead of using $S(m,w)$, define $B(w,i)$ to be a Boolean value representing whether item i is currently included in the most profitable packing with a weight of w. The updated pseudo-code is as follows:

Initialize f(w) to 0, B(w,i)=0 for all w,i
for i from 1 to n do:
 	for w from W to 0 do:
		if w[i] < W then:
                        let p be the profit of S(i-1,w-w[i])+{i}
	                if p > f(w) then:
		                f(w) = p
			        B(w,i) = 1
                                for j from 1 to i-1 do:
                                        B(w,j) = B(w-w[i],j)

Note this revised algorithm still runs in $O(Wn^{2})$ while only taking up $O(Wn)$ memory.

Greedy Heuristic algorithm

George Dantzig proposed a greedy approximation algorithm to unbounded knapsack problem which can also be used to solve the 0-1 QKP. The algorithm consists of two phrases: identify an initial solution and improve it.

First compute for each item, the total objective contribution realizable by selecting it, $p_{i}+\sum _{i\neq j}^{n}P_{ij}$, and sort the items in decreasing order of the potential value per unit of weight, $(p_{i}+\sum _{i\neq j}^{n}P_{ij})/w_{i}$. Then select the items with the maximal value-weight ratio into the knapsack until there is no space for more, which forms the initial solution. Starting with the initial solution, the improvement is conducted by pairwise exchange. For each item in the solution set, identify the items not in the set where swapping results in an improving objective. Select the pair with maximal improvement and swap. There are also possibilities that removing one from the set or adding one to the set will produce the greatest contribution. Repeat until there is no improving swapping. Specifically, the pseudo-code is as follows:

for i from 1 to n do:
        value[i] = p[i]
 	for j from 1 to n do:
                value[i] = value[i] + P[i][j]
        ratio[i] = value[i]/w[i]
sort ratio[i]
while sum<=W do
        add ratio[index] to T
        sum = sum + w
        index++
for i from 1 to n do
        delta[i] = p[i]
        for j from 1 to T.size-1 do
                delta[i] = delta[i] + P[i][j]
int max, swapIndex1, swapIndex2
repeat until max < 0 do
        for each item i in T do
                if delta[i] > max then
                        max = delta[i]
                        swapIndex1 = i
                        swapIndex2 = null
                for each item not in T do
                        if -delta[j] > max && w[j] < W-sum then
                                max = -delta[j]
                                swapIndex1 = null
                                swapIndex2 = j
                        delta[i][j] = delta[i]-delta[j]+P[i][j]
		        if delta[i][j] > max then
                                max = delta[i][j]
                                swapIndex1 = i
                                swapIndex2 = j
        swap i,j and update

The complexity class of this algorithm is $O(2^{n})$ since for the worst case every possible combination of items will be identified.

Related research topics

There is a link between the "decision" and "optimization" problems in that if there exists a polynomial algorithm that solves the "decision" problem, then one can find the maximum value for the optimization problem in polynomial time by applying this algorithm iteratively while increasing the value of k . On the other hand, if an algorithm finds the optimal value of optimization problem in polynomial time, then the decision problem can be solved in polynomial time by comparing the value of the solution output by this algorithm with the value of k . Thus, both versions of the problem are of similar difficulty. One theme in research literature is to identify what the "hard" instances of the knapsack problem look like, or viewed another way, to identify what properties of instances in practice might make them more amenable than their worst-case NP-complete behavior suggests. The goal in finding these "hard" instances is for their use in public key cryptography systems, such as the Merkle-Hellman knapsack cryptosystem.

See also

• Combinatorial auction
• Combinatorial optimization
• Continuous knapsack problem
• NP-completeness
• NP-hardness
• List of knapsack problems
• List of NP-complete problems
• Packing problem

References

• Pisinger, David. "David Pisinger's optimization codes". Retrieved 2016-11-09.
• Gallo, G; Hammer, PL; Simeone, B (1980). "Quadratic knapsack problems". Math.Program.Stud (12): 132–149.

External links

• C Code for Quadknap algorithm, by Alberto Caprara, David Pisinger, Polo Toth