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

${\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_{i}x_{j}:x\in X,x{\text{ binary}}\right\}}$

${\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\}.}$

While the binary variable x_i represents whether item i is included in the knapsack, ${\displaystyle p_{i}}$ is the profit earned by selecting item i and ${\displaystyle 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 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,^[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:

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

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

subject to

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

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

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

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

${\displaystyle x\in X,x}$ 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.^[14][15][16] The Glover formulation is shown below, where L_i and U_i are lower and upper bounds on ${\displaystyle \sum _{j=1,i\neq j}^{n}P_{ij}x_{j}}$, respectively:

LP2: maximize

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

subject to

${\displaystyle L_{i}x_{i}\leq z_{i}\leq U_{i}x_{i}}$ for ${\displaystyle i=1,\ldots ,n}$

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

${\displaystyle x\in X,x}$ binary

In the formulation LP2, we have replaced the expression ${\displaystyle \sum _{j=1,i\neq j}^{n}P_{ij}x_{i}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 ${\displaystyle n}$ auxiliary variables with ${\displaystyle 2n}$ constraints while standard linearization requires ${\displaystyle {n \choose 2}}$ auxiliary variables and ${\displaystyle 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. A convex program is to maximize a concave function or minimize a convex function on a convex set. A set S is convex if ${\displaystyle \forall u,v\in S}$, ${\displaystyle \lambda u+(1-\lambda )v\in S}$ where ${\displaystyle \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 ${\displaystyle f[\lambda u+(1-\lambda )v]\leq \lambda f(u)+(1-\lambda )f(v)}$. A function f is convex if ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle p^{T}x+x^{T}Px+\sum _{i=1}^{n}\left(\sum _{j=1,j\neq i}^{n}|P_{ij}|\right)(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, ${\displaystyle p_{i}+\sum _{i\neq j}^{n}P_{ij}}$, and sort the items in decreasing order of the potential value per unit of weight, ${\displaystyle (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 ${\displaystyle 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 proposed 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 in C and is 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 ${\displaystyle w\leq W}$, define ${\displaystyle 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

${\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_{i}x_{j}:\sum _{i=1}^{m}w_{i}=w,1\leq i\leq m\right\}.}$

Then, ${\displaystyle 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