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

摘要：

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

关键词：占优、占优组、分支定界、二次背包问题、整数规划、全局最优

所属期刊栏目：29

分类号：O221.4(运筹学)

资助基金：国家自然科学基金资助项目11271128

在线出版日期：2015-11-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：278-287