Quadratic knapsack problem

The quadratic knapsack problem (QKP), first introduced in 19th century, 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 items 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. The 0-1 quadratic knapsack problem is a variation of knapsack problems, combining 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:

[math]\displaystyle{ \text{maximize } \left\{\sum_{i=1}^n p_i x_i + \sum_{i=1}^n\sum_{j=1,i\neq j}^n P_{ij}x_ix_j: x\in X, x \text{ binary} \right\} }[/math]

[math]\displaystyle{ \text{subject to } X\equiv\left\{x \in \{0,1\}^n: \sum_{i=1}^n w_i x_i \leq W; x_i \in \{0,1\} \text{ for } i=1,\ldots, n \right\}. }[/math]

Here the binary variable x_i represents whether item i is included in the knapsack, [math]\displaystyle{ p_i }[/math] is the profit earned by selecting item i and [math]\displaystyle{ P_{ij} }[/math] 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. Applications of QKP in the field of computer science is more common after the early days: compiler design problem, clique problem, very large scale integration (VLSI) design. Additionally, pricing problems appear to be an application of QKP as described by Johnson et al.

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 known 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, 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:

// 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 [math]\displaystyle{ 2^n }[/math] subsets and for each legal candidate set, the running time of computing the values earned is [math]\displaystyle{ O(n^2) }[/math]. Thus, the efficiency class of brute-force algorithm is [math]\displaystyle{ (2^n n^2 )=\lambda(2^n) }[/math], 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

[math]\displaystyle{ \sum_{i=1}^n p_i x_i + \sum_{i=1}^n \left(\sum_{j=1,i\lt j}^n (P_{ij} + P_{ji}) z_{ij} \right). }[/math]

subject to

[math]\displaystyle{ z_{ij}\leq x_i }[/math] for all [math]\displaystyle{ (i,j), i\lt j }[/math]

[math]\displaystyle{ z_{ij}\leq x_j }[/math] for all [math]\displaystyle{ (i,j), i\lt j }[/math]

[math]\displaystyle{ x_i+x_j-1\leq z_{ij} }[/math] for all [math]\displaystyle{ (i,j), i\lt j }[/math]

[math]\displaystyle{ z_{ij}\geq 0 }[/math] for all [math]\displaystyle{ (i,j), i\lt j }[/math]

[math]\displaystyle{ x \in X, x }[/math] binary

In the formulation LP1, we have replaced the x_ix_j term with a continuous variable z_ij. This reformulates the QKP into a knapsack problem, which we can then solve optimally using standard solvers.

Glover's 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 [math]\displaystyle{ \sum_{j=1,i\neq j}^n P_{ij}x_j }[/math], respectively:

LP2: maximize

[math]\displaystyle{ \sum_{i=1}^n p_i x_i + \sum_{i=1}^nz_i }[/math]

subject to

[math]\displaystyle{ L_ix_i\leq z_i \leq U_ix_i }[/math] for [math]\displaystyle{ i=1,\ldots, n }[/math]

[math]\displaystyle{ \sum_{j=1,i\neq j}^nP_{ij} x_j - U_i(1-x_i)\leq z_i\leq \sum_{j=1,i\neq j}^nP_{ij} x_j-L_i(1-x_i) }[/math] for [math]\displaystyle{ i=1,\ldots, n }[/math]

[math]\displaystyle{ x \in X, x }[/math] binary

In the formulation LP2, we have replaced the expression [math]\displaystyle{ \sum_{j=1,i\neq j}^n P_{ij} x_i x_j }[/math] with a continuous variable z_i. Similarly, we can use standard solvers to solve the linearized problem. Note that Glover’s linearization only includes [math]\displaystyle{ n }[/math] auxiliary variables with [math]\displaystyle{ 2n }[/math] constraints while standard linearization requires [math]\displaystyle{ {n \choose 2} }[/math] auxiliary variables and [math]\displaystyle{ 3{n \choose 2} }[/math] 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. A convex program is to maximize a concave function or minimize a convex function on a convex set. A set S is convex if [math]\displaystyle{ \forall u,v\in S }[/math], [math]\displaystyle{ \lambda u+(1-\lambda)v\in S }[/math] where [math]\displaystyle{ \lambda \in [0,1] }[/math]. 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 [math]\displaystyle{ f[\lambda u+(1-\lambda)v]\leq \lambda f(u)+(1-\lambda)f(v) }[/math]. A function f is convex if [math]\displaystyle{ f[\lambda u+(1-\lambda)v]\geq \lambda f(u)+(1-\lambda)f(v) }[/math]. 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 [math]\displaystyle{ c^Tx+x^TCx }[/math] 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 [math]\displaystyle{ p^Tx+x^TPx+\sum_{i=1}^n \left(\sum_{j=1,j\neq i}^n|P_{ij}|\right)(x_i^2-x_i) }[/math] 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.

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, [math]\displaystyle{ p_i+\sum_{i\neq j}^n P_{ij} }[/math], and sort the items in decreasing order of the potential value per unit of weight, [math]\displaystyle{ (p_i+\sum_{i\neq j}^nP_{ij})/w_i }[/math]. 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 [math]\displaystyle{ O(2^n) }[/math] since for the worst case every possible combination of items will be identified.

Quadknap

Quadknap is an exact branch-and-bound algorithm proposed by Caprara et al., 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 in C and is available online.

Dynamic programming heuristic

While dynamic programming can generate optimal solutions to knapsack problems, dynamic programming approaches for QKP 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 [math]\displaystyle{ w\leq W }[/math], define [math]\displaystyle{ f(m,w) }[/math] to be the value of the most profitable packing of the first m items found with a total weight of w. That is, let

[math]\displaystyle{ f(m,w)=\max\left\{\sum_{i=1}^m p_i x_i + \sum_{i=1}^m\sum_{j=1,i\neq j}^m P_{ij}x_ix_j: \sum_{i=1}^m w_i=w,1\leq i\leq m \right\}. }[/math]

Then, [math]\displaystyle{ f(m,w) }[/math] 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 [math]\displaystyle{ f(m,w) }[/math] is the same with [math]\displaystyle{ f(m-1,w) }[/math]. Given that the item has a smaller weight compared with the desired weight, [math]\displaystyle{ f(m,w) }[/math] is either the same as [math]\displaystyle{ f(m-1,w) }[/math] 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. [math]\displaystyle{ f(m-1,w-w_m)+p_m+\sum_{i=1}^{m-1}P_{im}x_i }[/math]. To conclude, we have that

[math]\displaystyle{ f(m,w)= \begin{cases} \max f(m-1,w),f(m-1,w-w_m)+p_m+\sum_{i=1}^{m-1}P_{im}x_i & \text{if } w_m\leq w\\ f(m-1,w) & \text{otherwise} \end{cases} }[/math]

Note on efficiency class: Clearly the running time of this algorithm is [math]\displaystyle{ O(Wn^2) }[/math], 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 [math]\displaystyle{ O(Wn^2) }[/math] 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 [math]\displaystyle{ f(m,w) }[/math] since all the computations depend only on the results from the preceding stage.

Redefine [math]\displaystyle{ f(w) }[/math] to be the current value of the most profitable packing found by the heuristic. That is,

[math]\displaystyle{ f(w)=\max\left\{\sum_{i=1}^m p_i x_i + \sum_{i=1}^m \sum_{j=1,i\neq j}^m P_{ij}x_ix_j: \sum_{i=1}^m w_i=w,m\leq n \right\}. }[/math]

Accordingly, by dynamic programming we have that

[math]\displaystyle{ f(m)= \begin{cases} \max f(w),f(w-w_m)+p_m+\sum_{i=1}^{m-1}P_{im}x_i & \text{if } w_m\leq w, \\ f(w) & \text{otherwise.} \end{cases} }[/math]

Note this revised algorithm still runs in [math]\displaystyle{ O(Wn^2) }[/math] while only taking up [math]\displaystyle{ O(Wn) }[/math] memory compared to the previous [math]\displaystyle{ O(Wn^2) }[/math].

Related research topics

Researchers have studied 0-1 quadratic knapsack problems for decades. One focus is to find effective algorithms or effective heuristics, especially those with an outstanding performance solving real world problems. The relationship between the decision version and the optimization version of the 0-1 QKP should not be ignored when working with either one. On one hand, if the decision problem can be solved in polynomial time, then one can find the optimal solution by applying this algorithm iteratively. On the other hand, if there exists an algorithm that can solve the optimization problem efficiently, then it can be utilized in solving the decision problem by comparing the input with the optimal value.

Another theme in literature is to identify what are the "hard" problems. Researchers who study the 0-1 QKP often perform computational studies to show the superiority of their strategies. Such studies can also be conducted to assess the performance of different solution methods. For the 0-1 QKP, those computational studies often rely on randomly generated data, introduced by Gallo et al. Essentially every computational study of the 0-1 QKP utilizes data that is randomly generated as follows. The weights are integers taken from a uniform distribution over the interval [1, 50], and the capacity constraints is an integer taken from a uniform distribution between 50 and the sum of item weights. The objective coefficients, i.e. the values are randomly chosen from [1,100]. It has been observed that generating instances of this form yields problems with highly variable and unpredictable difficulty. Therefore, the computational studies presented in the literature may be unsound. Thus some researches aim to develop a methodology to generate instances of the 0-1 QKP with a predictable and consistent level of difficulty.

See also

• Knapsack problem
• Combinatorial auction
• Combinatorial optimization
• Continuous knapsack problem
• List of knapsack problems
• Packing problem

External links

• David Pisinger's Codes for different knapsack problem
• Codes for Quadratic Knapsack Problem