A Dynamic Programming Heuristic for the Quadratic Knapsack Problem
Adam Letchford (a.n.letchfordlancaster.ac.uk)
Abstract: It is well known that the standard (linear) knapsack problem can be solved exactly by dynamic programming in O(nc) time, where n is the number of items and c is the capacity of the knapsack. The quadratic knapsack problem, on the other hand, is NP-hard in the strong sense, which makes it unlikely that it can be solved in pseudo-polynomial time. We show however that the dynamic programming approach to the linear knapsack problem can be modified to yield a highly effective constructive heuristic for the quadratic version. In our experiments, the lower bounds obtained by our heuristic were consistently within a fraction of a percent of optimal. Moreover, the addition of a simple local search step enabled us to obtain the optimal solution of all instances considered.
Keywords: knapsack problems, integer programming, dynamic programming
Category 1: Combinatorial Optimization
Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )
Category 3: Other Topics (Dynamic Programming )
Citation: Eventually published as: F. Djeumou Fomeni & A.N. Letchford (2014) A dynamic programming heuristic for the quadratic knapsack problem. INFORMS J. Comput., 26(1), 173–182.
Entry Submitted: 03/17/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|