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

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

作　　者：高培旺[1] 封全喜[1] 

机构地区：[1]中南大学铁道校区数学科学与计算技术学院,湖南长沙410075

出　　处：《数学的实践与认识》2004年第4期109-114,共6页Mathematics in Practice and Theory

摘　　要：把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( 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).

关 键 词：整数线性规划 分枝定界法 割平面法 目标函数 

分 类 号：O221.1[理学—运筹学与控制论]