摘要
把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( 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).
出处
《数学的实践与认识》
CSCD
北大核心
2004年第4期109-114,共6页
Mathematics in Practice and Theory
