A Dynamic Programming Heuristic for the Quadratic Knapsack Problem
Franklin Djeumou Fomeni, Adam N. Letchford
INFORMS Journal on Computing · 2014 · Volume 26 · Issue 1
Abstract
It is well known that the standard (linear) knapsack problem can be solved exactly by dynamic programming in 𝒪 ( 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
Enable JavaScript for citation tools and additional paper interactions.