《计算机学报》文章摘要   全文下载
文章题目	二次背包问题的一种快速解法
作者	谢涛1) 陈火旺1) 康立山2)
作者单位	1）（国防科学技术大学计算机学院 长沙 410073） 2）（武汉大学软件工程国家重点实验室 武汉 430072）
发表年份	2004
发表月份	9期(1162—1169)
文章摘要	摘要 在分析了二次背包问题（QKP）精确算法的计算效率随利润矩阵密度下降的原因的基础上，提出了不受密度影响的QKP快速解法——利润欺骗法.在线性化QKP的目标上界估计中，利润欺骗法通过引进一适当正常数对称扩展Lagrangian乘子的变化范围，亚梯度优化算法能较快地找到一Lagrangian乘子矩阵，使对偶问题的解逼近线性化QKP问题的等式约束条件.通过提高目标函数的估计精度，利润欺骗法可以提高变量约简效率，降低分支决策深度.实例计算表明，快速算法的效率远高于精确算法，而且计算精度并不降低. 关键词 二次规划；二次背包问题；Lagrangian松弛；分支定界算法 中图法分类号 TP301