| 切割定界与整数分枝结合求解整数线性规划 |
| |
| 引用本文： | 高培旺,封全喜.切割定界与整数分枝结合求解整数线性规划[J].数学的实践与认识,2004,34(4):109-114. |
| |
| 作者姓名： | 高培旺 封全喜 |
| |
| 作者单位： | 中南大学铁道校区数学科学与计算技术学院,湖南,长沙,410075 |
| |
| 摘 要： | 把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( ILP)问题 .它利用目标函数等值面的移动来切去相应 ( LP)的可行域中含其非整数最优解但不含 ( ILP)可行解的“无用部分”,并将对应的目标函数值作为 ( ILP)目标最优值的一个上界 ;最后 ,通过 ( LP)最优解中非整数基变量的整数分枝来获得整数线性规划的最优解 .
|
| 关 键 词： | 整数线性规划 分枝定界法 割平面法 |
| 修稿时间： | 2001年8月28日 |
Combining a Cutting-Bound Method and the Integral Branch Principle for Solving Integer Linear Programming |
| |
| GAO Pei-wang,FENG Quan-xi.Combining a Cutting-Bound Method and the Integral Branch Principle for Solving Integer Linear Programming[J].Mathematics in Practice and Theory,2004,34(4):109-114. |
| |
| Authors: | GAO Pei-wang FENG Quan-xi |
| |
| Abstract: | 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). |
| |
| Keywords: | integer linear programming branch-and-bound method cutting plane |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
