Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
- 1 May 2007
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 19 (2) , 280-290
Abstract
The quadratic knapsack problem (QKP) calls for maximizing a quadratic objective function subject to a knapsack constraint. All coefficients are assumed to be nonnegative and all decision variables are binary. A new exact algorithm is presented, which makes use of aggressive reduction techniques to decrease the size of the instance to a manageable size. A cascade of upper bounds is used for the reduction, including an improved version of the Caprara-Pisinger-Toth bound based on upper planes and reformulation, and the Billionnet-Faye-Soutif bound based on Lagrangian decomposition. Generalized reduction techniques based on implicit enumeration are used to fix variables at their optimal values. In order to obtain lower bounds of high quality for the reduction, a core problem is solved, defined on a subset of variables. The core is chosen by merging numerous heuristic solutions found during the subgradient-optimization phase. The upper and lower bounding phases are repeated several times, each time improving the subgradient method used for finding the Lagrangian multipliers associated with the upper bounds. Having reduced the instance to a (hopefully) reasonable size, a branch and bound algorithm based on the Caprara-Pisinger-Toth framework is applied. Computational experiments are presented showing that several instances with up to 1,500 binary variables can be reduced to fewer than 100 variables. The remaining set of variables are easily handled through the exact branch and bound algorithm. In comparison to previous algorithms the framework does not only solve larger instances, but the algorithm also works well for instances with smaller densities of the profit matrix, which appear frequently when modeling various graph problems as quadratic knapsack problems.Keywords
This publication has 19 references indexed in Scilit:
- A hub location problem with fully interconnected backbone and access networksComputers & Operations Research, 2007
- Upper bounds and exact algorithms for -dispersion problemsComputers & Operations Research, 2006
- A new upper bound for the 0-1 quadratic knapsack problemEuropean Journal of Operational Research, 1999
- An extended formulation approach to the edge-weighted maximal clique problemEuropean Journal of Operational Research, 1996
- Linear programming for the 0–1 quadratic knapsack problemEuropean Journal of Operational Research, 1996
- Lagrangean methods for the 0–1 Quadratic Knapsack ProblemEuropean Journal of Operational Research, 1996
- Good solutions to discrete noxious location problems via metaheuristicsAnnals of Operations Research, 1992
- The discrete p-dispersion problemEuropean Journal of Operational Research, 1990
- Best network flow bounds for the quadratic knapsack problem1989
- Quadratic knapsack problems1980