Optimization Online


A Dynamic Programming Heuristic for the Quadratic Knapsack Problem

Adam Letchford (a.n.letchford***at***lancaster.ac.uk)
Franklin Djeumou Fomeni (f.djeumoufomeni***at***lancaster.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
Entry Accepted: 03/17/2012
Entry Last Modified: 05/31/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society