割平面法

求解整数规划问题的方法

割平面法主要用于求解整数规划问题的方法。1958年由美国格莫理提出。基本思路是：先不考虑整数性约束，求解相应的线性规划问题。若线性规划问题的最优解恰好是整数解，则此解即为整数规划问题的最优解。否则，就增加一个新的约束条件,称为割平面。割平面必须具有两条性质：（1）从线性规划问题的可行域中至少割掉的非整数最优解；（2)不割掉任何整数可行域，然后在缩小的可行域上继续解线性规划问题。重复以上做法，经有限次切割后，必可在缩小的可行域的一个整数极点上达到整数规划问题的最优解。

简介

混合整数线性规划（MILP）的割平面法通过将整数问题线性松弛为非整数线性问题，并对其进行求解，来求解 MILP 问题。线性规划理论说明，在温和的假定下（如果线性规划存在最优解，并且可行域不包含一条线），总存在一个极值点或顶点是最优的。检验所获的最优解是否为整数解。如否，则必然存在一线性不等式将最优点和真可行集的凸包分离。找到这样的不等式是分离问题，而这样的不等式就是切割。切割可以被加入到被松弛的线性规划中，使得当前的非整数解对松弛不再可行。该过程不断重复，直到找到最优整数解。

用于普遍的凸连续优化和变体的割平面法有不同的名称： Kelley 法， Kelley-Cheney-Goldstein 法和捆绑法。它们常用于不可微的凸最小化问题。对于这类问题，通常的可微优化的梯度法无法使用，而使用这些方法可以高效地得到凸目标函数及其次梯度。这种情况最常出现在双拉格朗日函数的凹优化中。另一种常见情形是 Dantzig-Wolfe分解应用于结构优化问题中，这类问题通常有含有指数级变量的表达式。通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面。

例，如上图1，单位立方体与切割平面。在三节点的旅行推销员问题中，该（弱）不等式表明每次旅行必须连接至少两个点。

Gomory 切割

切割平面法由 Ralph Gomory 在 20世纪 50 年代提出，用于解决整数规划和混合整数规划问题。然而，当时的大多数专家，包括 Gomory 自己都认为由于数值上的不稳定性，这种方法没有实际运用价值；同时由于求解过程中需要进行过多轮的切割，该方法可能是无效的。而在 19 世纪 90 年代中期，Gérard Cornuéjols 和同事发现切割平面法与分支定界法结合（称作分支切割法）时效率很高，并且能有效克服数值不稳定性。现在，所有的商用 MILP 求解器都或多或少地使用了 Gomory 切割。Gomory 切割可通过单一单纯形表格生成，相比于其他计算成本高昂、甚至分离为 NP-困难的其他切割法来说十分高效。在其他 MILP 的普遍切割法中，提升和投影割平面法明显优于 Gomory 切割。

设一整数规划问题被表达为其标准形式：

该方法首先将为整数的约束进行松弛，并求解相应的线性规划问题，得出基本可行解。在几何层面上，该解为含有所有可行解的凸多胞形的一个顶点。如果该顶点不是整数点，则该方法将凸多胞形分为两部分，一部分含有该顶点的超平面，另一部分含有所有整数解。该超平面随即作为额外的线性约束加入到问题中，构成修正的线性问题，以排除前一步发现的顶点。随后求解新的线性问题，重复这一过程，直到发现整数解。

使用单纯形法求解线性问题会产生一组如下形式的方程

其中是基本变量，是非基本变量。重写方程，使整数部分位于等号左边，小数部分位于等号右边：

对于任意位于可行域的整数点，等号右边小于 1 ，而等号左边为整数，因此两边共同的取值必然小于或等于 0 。因此不等式

对于可行域内的所有整数点必须成立。此外，在基本可行解中，非基本变量都为 0 ，而且基本可行解中如果不是整数，

所以上方的不等式排除了基本可行解，并且是符合需求的一次切割。通过将新的松弛变量引入不等式中，新的约束得以加入到线性问题中：

基本步骤

(1)先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。

在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。

(2)求一个“切割不等式”及添加到整数规划的约束条件中去，即对上述线性规划问题的可行域进行“切割”，然后返回步骤1。

基本思路

用割平面法求解整数规划的基本思路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止．如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解．这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)．而把所有的整数解都保留下来，故称新增加的约束条件为割平面．当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解．即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。

凸优化

切割平面法也适用于非线性规划。其基本原理是通过封闭半空间的有限集估算非线性（凸）问题的可行域，并对一系列的线性问题估算进行求解。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省