目标等值面切割定界与割平面法结合求解整数规划

Combining Cutting-and-bound Principle of Objective Equivalent Plane with the Cutting Plane Method for Solving Integer Linear Programming

把目标等值面切割定界原理与Gomory的割平面法结合起来求解整数线性规划 (ILP)问题 .首先通过目标函数等值面的平行移动来切去 (LP)可行域中含其非整数最优解但不含 (ILP)可行解的“无用部分” ;然后 ,应用Gomory的割平面在通过 (ILP)最优解的目标等值面上切割其最优解 .

This paper combines a cutting_and_bound principle of objective equivalent plane with the Gomory cutting plane method for solving integer linear programming problems.In the algorithm presented,the 'insignificant parts' of the feasible domain of (LP) associated with (ILP) would be cut off by decreasing the optimal objective value of the (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 on an objective equivalent plane through the cutting of the Gomory's cutting planes.