切割平面法

在数学优化中，切割平面法是通过线性不等式对可行集或目标函数进行迭代性优化（即切割）的优化方法的涵盖性术语。该过程通常用来发现混合整数线性规划（MILP）问题的整数解，也可以用来解决常规的、未必可微的凸优化问题。利用切割平面法求解 MILP 由 Ralph E. Gomory 引入。

单位立方体与切割平面

{\displaystyle x_{1}+x_{2}+x_{3}\geq 2}

。在三节点的旅行推销员问题中，该（弱）不等式表明每次旅行必须连接至少两个点。

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

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

Gomory 切割

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

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

{\begin{aligned}{\mbox{Maximize  }}&c^{T}x\\{\mbox{s.t.}}&Ax=b,\\&x\geq 0,\,x_{i}{\mbox{ all integers}}.\\\end{aligned}}

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

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

x_{i}+\sum {\bar {a}}_{i,j}x_{j}={\bar {b}}_{i}

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

x_{i}+\sum \lfloor {\bar {a}}_{i,j}\rfloor x_{j}-\lfloor {\bar {b}}_{i}\rfloor ={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum ({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}

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

{\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum ({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}\leq 0

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

{\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum ({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor >0

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

x_{k}+\sum (\lfloor {\bar {a}}_{i,j}\rfloor -{\bar {a}}_{i,j})x_{j}=\lfloor {\bar {b}}_{i}\rfloor -{\bar {b}}_{i},\,x_{k}\geq 0,\,x_{k}{\mbox{ an integer}}.

凸优化

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

另见

Benders 分解法
分支切割法
分支定界法
列生成法
Dantzig-Wolfe 分解

参考文献

Marchand, Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence. (PDF). Discrete Applied Mathematics. 2002, (123): 387–446.
Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publications. ISBN 0-486-43227-0
Cornuéjols, Gérard (2008). Valid Inequalities for Mixed Integer Linear Programs. Mathematical Programming Ser. B, (2008) 112:3-44. 页面存档备份，存于
Cornuéjols, Gérard (2007). Revival of the Gomory Cuts in the 1990s. Annals of Operations Research, Vol. 149 (2007), pp. 63–66. 页面存档备份，存于

外部链接

"Integer Programming" Section 9.8 页面存档备份，存于 Applied Mathematical Programming Chapter 9 Integer Programming (full text). Bradley, Hax, and Magnanti (Addison-Wesley, 1977)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.