二次背包问题的一种快速解法

摘要

在分析了二次背包问题(QKP)精确算法的计算效率随利润矩阵密度下降的原因的基础上,提出了不受密度影响的QKP快速解法--利润欺骗法.在线性化QKP的目标上界估计中,利润欺骗法通过引进一适当正常数对称扩展Lagrangian乘子的变化范围,亚梯度优化算法能较快地找到一Lagrangian乘子矩阵,使对偶问题的解逼近线性化QKP问题的等式约束条件.通过提高目标函数的估计精度,利润欺骗法可以提高变量约简效率,降低分支决策深度.实例计算表明,快速算法的效率远高于精确算法,而且计算精度并不降低.