Quadratic knapsack problem

The quadratic knapsack problem (QKP), first introduced in 19th century,^[1] is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of item to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al.^[2] 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_{ij}$ 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.

Application

As one might expect, QKP has a wide range of applications including telecommunication, transportation network, computer science and economics. In fact, Witzgall first discussed QKP when selecting sites for satellite stations in order to maximize the global traffic with respect to a budget constraint. Similar model applies to problems like considering the location of airports, railway stations, or freight handling terminals.^[3] Applications of QKP in the field of computer science is more common after the early days: compiler design problem,^[4] clique problem,^[5]^[6] very large scale integration (VLSI) design.^[7] Additionally, pricing problems appear to be an application of QKP as described by Johnson et al.^[8]

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.^[9] 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.

While no available efficient algorithm exists in the literature, there is a pseudo-polynomial time 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 operation research (OR) problems, there are limited efficient algorithms that can solve 0-1 quadratic knapsack problems. Available algorithms include but are not limited to brute force, linearization,^[10] and convex reformulation. Just like other NP-hard problems, it is usually enough to find a workable solution even if it is not necessarily optimal. Heuristic algorithms based on greedy algorithm, dynamic programming can give a relatively “good” solution to the 0-1 QKP efficiently.

Brute force

The brute force 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:

 1 // Input:
 2 // Profits (stored in array p)
 3 // Quadratic profits (stored in matrix P)
 4 // Weights (stored in array w)
 5 // Number of items (n)
 6 // Knapsack capacity (W)
 7 
 8 int max =0
 9 for all subset S do
10 	int value, weight = 0
11  	for i from 0 to S.size-1 do:
12 		value = value +p[i]
13 		weight = weight +w[i]
14 			for j from i+1 to S.size-1 do: 
15 				value = value + P[i][j]
16 	if weight <= W then:
17 		if value > max then:	
18 			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 force algorithm is $(2^{n}n^{2})=\lambda (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.^[11]^[12]^[13]

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.^[14]^[15]^[16] 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. Note that Glover’s linearization only includes $n$ auxiliary variables with $4n$ constraints while standard linearization requires ${{n} \choose {2}}$ auxiliary variables and $3{{n} \choose {2}}$ constraints to achieve linearity.

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. However, when the program is convex, any local maximum is the global maximum. A convex program is to maximize a concave function or minimize a convex function on a convex set. A set S is convex if $\forall u,v\in S$ , $\lambda u+(1-\lambda )v\in S$ where $\lambda \in [0,1]$ . That is to say, any point between two points in the set must also be an element of the set. A function f is concave if $f[\lambda u+(1-\lambda )v]\leq \lambda f(u)+(1-\lambda )f(v)$ . A function f is convex if $f[\lambda u+(1-\lambda )v]\geq \lambda f(u)+(1-\lambda )f(v)$ . Informally, a function is concave if the line segment connecting two points on the graph lies above or on the graph, while a function is convex if below or on the graph. 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 a diagonally dominant matrix and thus a positive semi-definite. This reformulation can be solved using a standard commercial mixed-integer quadratic package.^[17]

Greedy Heuristic algorithm

George Dantzig^[18] 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. The complexity class of this algorithm is $O(2^{n})$ since for the worst case every possible combination of items will be identified.

Quadknap

Quadknap is an exact branch-and-bound algorithm raised by Caprara et al.,^[19] where upper bounds are computed by considering a Lagrangian relaxation which approximate a difficult problem by a simpler problem and penalizes violations of constraints using Lagrange multiplier to impost a cost on violations. Quadknap releases the integer requirement when computing the upper bounds. Suboptimal Lagrangian multipliers are derived from sub-gradient optimization and provide a convenient reformulation of the problem. This algorithm is quite efficient since Lagrangian multipliers are stable, and suitable data structures are adopted to compute a tight upper bound in linear expected time in the number of variables. This algorithm was reported to generate exact solutions of instances with up to 400 binary variables, i.e., significantly larger than those solvable by other approaches. The code was written C language and available online.^[20]

Dynamic programming heuristic

While dynamic programming can generate optimal solutions to knapsack problems, dynamic programming approaches for QKP^[21] can only yield a relatively good quality 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)=\left\{{\begin{array}{l}\max f(m-1,w),f(m-1,w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}{\mbox{ if }}w_{m}\leq w\\f(m-1,w){\mbox{ otherwise }}\end{array}}\right.$ .

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.

Revised dynamic programming algorithm

Note that the previous algorithm requires $O(Wn^{2})$ space for storing the current packing of items 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.

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(m)=\left\{{\begin{array}{l}\max f(w),f(w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}{\mbox{ if }}w_{m}\leq w\\f(w){\mbox{ otherwise }}\end{array}}\right.$ .

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

Notes

↑ C., Witzgall (1975). "Mathematical methods of site selection for Electronic Message Systems (EMS)". NBS Internal report. doi:10.6028/nbs.ir.75-737.
↑ Gallo, G.; Hammer, P.L.; Simeone, B. (1980). "Quadratic knapsack problems". Mathematical Programming Studies Combinatorial Optimization: 132–149. doi:10.1007/bfb0120892.
↑ Rhys, J.M.W. (1970). "A Selection Problem of Shared Fixed Costs and Network Flows". Management Science. 17 (3): 200–207. doi:10.1287/mnsc.17.3.200.
↑ Helmberg, C.; Rendl, F.; Weismantel, R. (1996). "Quadratic knapsack relaxations using cutting planes and semidefinite programming". Integer Programming and Combinatorial Optimization Lecture Notes in Computer Science: 175–189. doi:10.1007/3-540-61310-2_14.
↑ Dijkhuizen, G.; Faigle, U. (1993). "A cutting-plane approach to the edge-weighted maximal clique problem". European Journal of Operational Research. 69 (1): 121–130. doi:10.1016/0377-2217(93)90097-7.
↑ Park, Kyungchul; Lee, Kyungsik; Park, Sungsoo (1996). "An extended formulation approach to the edge-weighted maximal clique problem". European Journal of Operational Research. 95 (3): 671–682. doi:10.1016/0377-2217(95)00299-5.
↑ Ferreira, C.E.; Martin, A.; Souza, C.C.De; Weismantel, R.; Wolsey, L.A. (1996). "Formulations and valid inequalities for the node capacitated graph partitioning problem". Mathematical Programming. 74 (3): 247–266. doi:10.1007/bf02592198.
↑ Johnson, Ellis L.; Mehrotra, Anuj; Nemhauser, George L. (1993). "Min-cut clustering". Mathematical Programming. 62 (1- 3): 133–151. doi:10.1007/bf01585164.
↑ Garey, Michael R.; Johnson, David S. (1979). Computers and intractibility: A guide to the theory of NP completeness. New York: Freeman and Co.
↑ Adams, Warren P.; Sherali, Hanif D. (1986). "A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems". Management Science. 32 (10): 1274–1290. doi:10.1287/mnsc.32.10.1274.
↑ Adams, Warren P.; Forrester, Richard J.; Glover, Fred W. (2004). "Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs". Discrete Optimization. 1 (2): 99–120. doi:10.1016/j.disopt.2004.03.006.
↑ Adams, Warren P.; Forrester, Richard J. (2005). "A simple recipe for concise mixed 0-1 linearizations". Operations Research Letters. 33 (1): 55–61. doi:10.1016/j.orl.2004.05.001.
↑ Adams, Warren P.; Forrester, Richard J. (2007). "Linear forms of nonlinear expressions: New insights on old ideas". Operations Research Letters. 35 (4): 510–518. doi:10.1016/j.orl.2006.08.008.
↑ Glover, Fred; Woolsey, Eugene (1974). "Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program". Operations Research. 22 (1): 180–182. doi:10.1287/opre.22.1.180.
↑ Glover, Fred (1975). "Improved Linear Integer Programming Formulations of Nonlinear Integer Problems". Management Science. 22 (4): 455–460. doi:10.1287/mnsc.22.4.455.
↑ Glover, Fred; Woolsey, Eugene (1973). "Further Reduction of Zero-One Polynomial Programming Problems to Zero-One linear Programming Problems". Operations Research. 21 (1): 156–161. doi:10.1287/opre.21.1.156.
↑ Bliek, Christian; Bonami, Pierre; Lodi, Andrea (2014). "Solving Mixed-Integer Quadratic Programming problems with IBM-CPLEX: a progress report" (PDF).
↑ Dantzig, George B. (1957). "Discrete-Variable Extremum Problems". Operations Research. 5 (2): 266–288. doi:10.1016/j.disopt.2004.03.006.
↑ Caprara, Alberto; Pisinger, David; Toth, Paolo (1999). "Exact Solution of the Quadratic Knapsack Problem". INFORMS Journal on Computing. 11 (2): 125–137. doi:10.1287/ijoc.11.2.125.
↑ "Quadknap". Retrieved 2016-12-03.
↑ Fomeni, Franklin Djeumou; Letchford, Adam N. (2014). "A Dynamic Programming Heuristic for the Quadratic Knapsack Problem". INFORMS Journal on Computing. 26 (1): 173–182. doi:10.1287/ijoc.2013.0555.
↑ Forrester, Richard J.; Adams, Warren P.; Hadavas, Paul T. (2009). "Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem.". Naval Research Logistics. doi:10.1002/nav.20364.

External links

This article is issued from Wikipedia - version of the 12/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Quadratic knapsack problem

Definition

Application

Computational Complexity

Solving

Brute force

Linearization

Standard Linearization

Glover'Linearization

Convex quadratic reformulation

Greedy Heuristic algorithm

Quadknap

Dynamic programming heuristic

Dynamic programming algorithm

Revised dynamic programming algorithm

Related research topics

See also

Notes

External links