An approximate dynamic programming approach to convex quadratic knapsack problems
An approximate dynamic programming approach to convex quadratic knapsack problems
复制标题
DOI：
10.1016/j.cor.2004.07.012
复制
发表时间：
2006-03
期刊：
影响因子：
--
通讯作者：
Zhongsheng Hua;Bin Zhang;L. Liang
中科院分区：
文献类型：
--
作者：
Zhongsheng Hua;Bin Zhang;L. Liang
二次背包问题（QKP）是整数优化和组合优化中的一个重要问题，而目前求解一般QKP问题的有效算法非常有限。本文提出了一种求解凸QKP问题的近似动态规划（ADP）方法，其中变量可以取任意整数值，且所有系数都是真实的数。我们使用（a）连续二次规划松弛（CQPR）和（B）CQPR解的积分部分来近似函数值。我们提出了一种新的启发式，自适应固定的变量根据CQPR的解决方案。我们报告的计算结果与多达200个整数变量的QKP。我们的数值结果表明，新的启发式产生高质量的解决方案，大规模的QKP快速和鲁棒性。
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 (ADP) 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.