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.
Definition Specifically, the 0–1 quadratic knapsack problem has the following form:
maximize { ∑ i = 1 n p i x i + ∑ i = 1 n ∑ j = 1 , i ≠ j n P i j x i x j : x ∈ X , x binary } {\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\}}
subject to X ≡ { x ∈ { 0 , 1 } n : ∑ i = 1 n w i x i ≤ W ; x i ∈ { 0 , 1 } for i = 1 , … , n } . {\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\}.}
Here the binary variable xi represents whether item i is included in the knapsack, p i {\displaystyle p_{i}} is the profit earned by selecting item i and P i j {\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. 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 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:
… excerpt ends here. Continue reading the full article.
