Quadratic knapsack problem
≈ 7 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 the knapsack problem, combining the features of the 0-1 knapsack problem and the 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 the knapsack problem, combining the features of the 0-1 knapsack problem and the quadratic knapsack problem. \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\} \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\}.
Here 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. // 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 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-force algorithm is (2^n n^2 )=\lambda(2^n) , being exponential. \sum_{i=1}^n p_i x_i + \sum_{i=1}^n \left(\sum_{j=1,i subject to z_{ij}\leq x_i for all (i,j), i z_{ij}\leq x_j for all (i,j), i x_i+x_j-1\leq z_{ij} for all (i,j), i z_{ij}\geq 0 for all (i,j), i x \in X, x binary In the formulation LP1, we have replaced the x i x 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.
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,i\neq j}^n P_{ij}x_j , respectively: LP2: maximize \sum_{i=1}^n p_i x_i + \sum_{i=1}^nz_i subject to L_ix_i\leq z_i \leq U_ix_i for i=1,\ldots, n \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) for i=1,\ldots, n x \in X, x binary In the formulation LP2, we have replaced the expression \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 linearized problem. Note that Glover's linearization only includes n auxiliary variables with 2n constraints while standard linearization requires {n \choose 2} auxiliary variables and 3{n \choose 2} constraints to achieve linearity. The objective function can be written as c^Tx+x^TCx 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^Tx+x^TPx+\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. 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\}. 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)= \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} 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 (and furthermore it provides no guarantee to reach the optimal solution). 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\}.
Accordingly, by dynamic programming we have that 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} Note this revised algorithm still runs in O(Wn^2) while only taking up O(Wn) memory compared to the previous O(Wn^2) .
See also
Knapsack problem Combinatorial auction Combinatorial optimization Continuous knapsack problem List of knapsack problems Packing problem
Notes
External links
David Pisinger's Codes for different knapsack problem Codes for Quadratic Knapsack Problem
Text derived from https://en.wikipedia.org/w/index.php?oldid=1314216629 under CC BY-SA 4.0; modifications have been made.