用割平面法求解整数规划

割平面法主要用于求解整数规划问题。1958是美国蛾摩拉提出来的。基本思想是在不考虑整数约束的情况下，求解相应的线性规划问题。如果线性规划问题的最优解恰好是整数解，那么这个解就是整数规划问题的最优解。否则，将添加一个新的约束，称为切割平面。

割平面必须具有两个性质:至少是从线性规划问题的可行域割出的非整数最优解；不截掉任何整数可行域，然后在约简的可行域上继续求解线性规划问题。通过重复上述实践，在有限次切割之后，整数规划问题的最优解可以在缩减的可行域的整数极点处获得。

割平面法是一种比较简单的求解整数规划的方法，由美国学者R.E.GoMory在1958中提出。其基本思想与分枝定界法基本相同，即在不考虑变量整数约束的情况下，用单纯形法求解相应的线性规划。

如果得到的最优解是整数解，那么它也是原整数规划问题的最优解。3如果最优解不是整数解，那么分支定界法通过任意选择一个带分数值的变量Xk=bk，将原整数规划分成两个分支。

其实质是将原可行域R分成两个与坐标轴垂直的平行平面Xk=[bk]和Xk=[bk]+1的可行域R1和R2，去掉两个平行平面之间不含整数解的可行域部分以缩小可行域。

割平面法是RalphGomory在20世纪50年代提出的，用于求解整数规划和混合整数规划。但当时的大多数专家，包括戈莫里本人，都认为这种方法因为数值不稳定，没有实用价值；同时，由于求解过程中需要多轮切割，这种方法也可能无效。