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.
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.
Available algorithms include but are not limited to brute force, linearization,[10] and convex reformulation.
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.
subsets and for each legal candidate set, the running time of computing the values earned is
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.
[11][12][13] The first one is the standard linearization strategy, as shown below: In the formulation LP1, we have replaced the xixj term with a continuous variable zij.
This reformulates the QKP into a knapsack problem, which we can then solve optimally using standard solvers.
[14][15][16] The Glover formulation is shown below, where Li and Ui are lower and upper bounds on
Note that nonlinear programs are hard to solve due to the possibility of being stuck at a local maximum.
We need to make P a positive semi-definite matrix in order to reformulate a convex function.
by applying results from linear algebra, where P is a diagonally dominant matrix and thus a positive semi-definite.
[17] George Dantzig[18] proposed a greedy approximation algorithm to unbounded knapsack problem which can also be used to solve the 0-1 QKP.
, and sort the items in decreasing order of the potential value per unit of weight,
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.
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.
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.
[20] 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.
space for storing the current packing of items for all m,w, which may not be able to handle large-size problems.
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.
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.
It has been observed that generating instances of this form yields problems with highly variable and unpredictable difficulty.
Thus some researches aim to develop a methodology to generate instances of the 0-1 QKP with a predictable and consistent level of difficulty.