二次整数背包问题的新算法

摘要

给出了一种求解一般二次整数背包问题(quadratic integer knapsack problem,QIKP)的新算法.该方法把占优的概念与分支定界思想结合,旨在寻求全局最优解.对QIKP给出了占优的定义,通过变量系数之间的关系,很容易找到占优组和极小占优组,从而删除可行域中那些非最优点.新的占优定义对凹的二次函数尤其有效.在理论证明的基础上,设计相应的算法,并进行了数值计算.结果显示,在随机产生的例子中,该算法是有效的,并且与传统的分支定界算法相比,得到了更好的最优解,最优值有了较大的提升.