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

Improvement of bound-and-stopped algorithm forinteger linear programs

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

This paper presented an improvement of the bound-and-stopped algorithm for general integer linear programming problems. This algorithm used the objective function hyperplane to intersect the binding constraints cone of the linear programming relaxation problem to form a simplex. Next, introduced a series of parallel slices to cut the simplex to produce the lower dimensional polyhedrons. Finally, carried out the stopped search procedure in the polyhedrons on the slices. Since the vertices of the simplex and the polyhedrons on the slices could directly be determined by the formulas, and the intervals of the variables in the polyhedrons on the slices were narrower, the algorithm was convenient and efficient. It was partially validated by the computational test on some classical and randomly-generated numerical examples.