TY - JOUR

T1 - A dynamic programming heuristic for the quadratic knapsack problem

AU - Djeumou Fomeni, Franklin

AU - Letchford, Adam

PY - 2014/2

Y1 - 2014/2

N2 - 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.

AB - 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.

KW - Knapsack problems

KW - integer programming

KW - dynamic programming

U2 - 10.1287/ijoc.2013.0555

DO - 10.1287/ijoc.2013.0555

M3 - Journal article

VL - 26

SP - 173

EP - 182

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1526-5528

IS - 1

ER -