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

A Fast Algorithm of Quadratic Knapsack Problem

作　　者：谢涛[1] 陈火旺[1] 康立山[2] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073 [2]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《计算机学报》2004年第9期1162-1169,共8页Chinese Journal of Computers

基　　金：国家自然科学基金 (60 1 330 1 0;6990 30 1 0 )资助

摘　　要：在分析了二次背包问题 (QKP)精确算法的计算效率随利润矩阵密度下降的原因的基础上 ,提出了不受密度影响的QKP快速解法———利润欺骗法 .在线性化QKP的目标上界估计中 ,利润欺骗法通过引进一适当正常数对称扩展Lagrangian乘子的变化范围 ,亚梯度优化算法能较快地找到一Lagrangian乘子矩阵 ,使对偶问题的解逼近线性化QKP问题的等式约束条件 .通过提高目标函数的估计精度 ,利润欺骗法可以提高变量约简效率 ,降低分支决策深度 .实例计算表明 ,快速算法的效率远高于精确算法 ,而且计算精度并不降低 .The cause that the computational efficiency of the fast algorithm for quadratic knapsack problems (QKP) decreases with the density of positive profits, has been theoretically analyzed. A profit swindling-based fast algorithm which is not subject to the density of positive profits is specially proposed for QKP with non-positive profits. In the upper bound computing of the linearized QKP, the fast algorithm symmetrically expands the domain of Lagrangian multipliers by increasing all profits by an appropriate positive constant, so that the sub-gradient algorithm can obtain an optimal Lagrangian multiplier matrix and the solution to the dual problem approach the equality constrains of the linearized QKP. The improved estimation precision of the optimal value further increases the reduction efficiency, and eventually decreases the branching depth of the branch-and-bound algorithm. Computational results show that this profit swindling-based fast algorithm greatly exceeds the exact QKP algorithm in overall efficiency, without exactness reduction.

关 键 词：二次规划 二次背包问题 LAGRANGIAN松弛 分支定界算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]