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:
Here the binary variable xi represents whether item i is included in the knapsack, is the profit earned by selecting item i and 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 subsets and for each legal candidate set, the running time of computing the values earned is . Thus, the efficiency class of brute-force algorithm is , 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