12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > A dynamic programming heuristic for the quadrat...
View graph of relations

« Back

A dynamic programming heuristic for the quadratic knapsack problem

Research output: Contribution to journalJournal article

Published

Journal publication date02/2014
JournalINFORMS Journal on Computing
Journal number1
Volume26
Number of pages10
Pages173-182
Early online date22/07/13
Original languageEnglish

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.