An approximate dynamic programming approach to convex quadratic knapsack problems

An approximate dynamic programming approach to convex quadratic knapsack problems

0.00 Avg rating0 Votes
Article ID: iaor20072063
Country: United Kingdom
Volume: 33
Issue: 3
Start Page Number: 660
End Page Number: 673
Publication Date: Mar 2006
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

Quadratic knapsack problem (QKP) has a central role in integer and combinatorial optimization, while efficient algorithms to general QKPs are currently very limited. We present an approximate dynamic programming approach for solving convex QKPs where variables may take any integer value and all coefficients are real numbers. We approximate the function value using (a) continuous quadratic programming relaxation (CQPR), and (b) the integral parts of the solutions to CQPR. We propose a new heuristic which adaptively fixes the variables according to the solution of CQPR. We report computational results for QKPs with up to 200 integer variables. Our numerical results illustrate that the new heuristic produces high-quality solutions to large-scale QKPs fast and robustly.

Reviews

Required fields are marked *. Your email address will not be published.