切割定界与整数分枝结合求解整数线性规划

Combining a Cutting-Bound Method and the Integral Branch Principle for Solving Integer Linear Programming

把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( ILP)问题 .它利用目标函数等值面的移动来切去相应 ( LP)的可行域中含其非整数最优解但不含 ( ILP)可行解的“无用部分”,并将对应的目标函数值作为 ( ILP)目标最优值的一个上界 ;最后 ,通过 ( LP)最优解中非整数基变量的整数分枝来获得整数线性规划的最优解 .

This paper combines a improved cutting-bound method and the integral branch principle for solving integer linear programming problems. In the algorithm ″insignificant parts″ of the feasible domain of (LP) associated with (ILP) would be cut off by decreasing the optimal objective value of (LP), and simultaneously, the corresponding objective value is taken as an upper bound to the solution of (ILP). Finally, the solutions to (ILP) would be obtained through the integral branches of non-integer basic variables in the optimal solution of (LP).