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

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