Home > Research > Publications & Outputs > A dynamic programming heuristic for the quadrat...

Associated organisational unit

Electronic data

Links

Text available via DOI:

View graph of relations

A dynamic programming heuristic for the quadratic knapsack problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
<mark>Journal publication date</mark>02/2014
<mark>Journal</mark>INFORMS Journal on Computing
Issue number1
Volume26
Number of pages10
Pages (from-to)173-182
Publication StatusPublished
Early online date22/07/13
<mark>Original language</mark>English

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.