  


A Dynamic Programming Heuristic for the Quadratic Knapsack Problem
Adam Letchford (a.n.letchfordlancaster.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 NPhard in the strong sense, which makes it unlikely that it can be solved in pseudopolynomial 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. Download: Entry Submitted: 03/17/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  