求解整数线性规划问题的定界阻止算法的改进

摘要：

在现有求解整数线性规划问题的定界阻止算法的基础上提出了一种改进.该算法通过目标函数超平面截线性规划松弛问题的有效约束锥而形成一个单纯形;然后,引入一串平行片来切割该单纯形产生更低维的凸多面体;最后,在片上的这些凸多面体上执行阻止搜寻程序.由于单纯形和片上凸多面体的极顶点可以直接通过公式计算,且变量在片上凸多面体上的取值区间更窄,改进的定界阻止算法既方便又高效,这得到了一些经典算例和随机产生的算例的验证.

关键词：线性规划、整数规划、目标函数超平面、单纯形、定界阻止算法

所属期刊栏目：26

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

资助基金：广西自然科学基金资助项目桂科自0728260

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

页数：共3页

页码：4471-4473