切割平面法

在數學最佳化中，切割平面法是通過線性不等式對可行集或目標函數進行迭代性最佳化（即切割）的最佳化方法的涵蓋性術語。該過程通常用來發現混合整數線性規劃（MILP）問題的整數解，也可以用來解決常規的、未必可微的凸最佳化問題。利用切割平面法求解 MILP 由 Ralph E. Gomory 引入。

單位立方體與切割平面 ${\displaystyle {\displaystyle x_{1}+x_{2}+x_{3}\geq 2}}$。 在三節點的旅行推銷員問題中，該（弱）不等式表明每次旅行必須連接至少兩個點。

MILP 的切割平面法通過將整數問題線性鬆弛為非整數線性問題，並對其進行求解，來求解 MILP 問題。線性規劃理論說明，在溫和的假定下（如果線性規劃存在最佳解，並且可行域不包含一條線），總存在一個極值點或頂點是最佳的。 檢驗所獲的最佳解是否為整數解。如否，則必然存在一線性不等式將最佳點和真可行集的凸包分離。找到這樣的不等式是分離問題，而這樣的不等式就是切割。 切割可以被加入到被鬆弛的線性規劃中，使得當前的非整數解對鬆弛不再可行。該過程不斷重複，直到找到最佳整數解。

用於普遍的凸連續最佳化和變體的切割平面法有不同的名稱： Kelley 法， Kelley-Cheney-Goldstein 法和捆綁法。它們常用於不可微的凸最小化問題。對於這類問題，通常的可微最佳化的梯度法無法使用，而使用這些方法可以高效地得到凸目標函數及其次梯度。這種情況最常出現在雙拉格朗日函數的凹最佳化中。另一種常見情形是 Dantzig-Wolfe 分解應用於結構最佳化問題中，這類問題通常有含有指數級變數的表達式。通過延遲列生成法按需生成這些變數等同於在對應的對偶問題上切割平面。

Gomory 切割

切割平面法由 Ralph Gomory 在 20 世紀 50 年代提出，用於解決整數規劃和混合整數規劃問題。然而，當時的大多數專家，包括 Gomory 自己都認為由於數值上的不穩定性，這種方法沒有實際運用價值；同時由於求解過程中需要進行過多輪的切割，該方法可能是無效的。而在 20 世紀 90 年代中期，Gérard Cornuéjols 和同事發現切割平面法與分支定界法結合（稱作分支切割法）時效率很高，並且能有效克服數值不穩定性。現在，所有的商用 MILP 求解器都或多或少地使用了 Gomory 切割。Gomory 切割可通過單一單體表格生成，相比於其他計算成本高昂、甚至分離為 NP-困難的其他切割法來說十分高效。在其他 MILP 的普遍切割法中，提升和投影割平面法明顯優於 Gomory 切割。

設一整數規劃問題被表達為其標準形式：

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

該方法首先將 ${\displaystyle x_{i}}$為整數的約束進行鬆弛，並求解相應的線性規劃問題，得出基本可行解。在幾何層面上，該解為含有所有可行解的凸多胞形的一個頂點。如果該頂點不是整數點，則該方法將凸多胞形分為兩部分，一部分含有該頂點的超平面，另一部分含有所有整數解。該超平面隨即作為額外的線性約束加入到問題中，構成修正的線性問題，以排除前一步發現的頂點。隨後求解新的線性問題，重複這一過程，直到發現整數解。

使用單體法求解線性問題會產生一組如下形式的方程

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

其中 ${\displaystyle x_{i}}$ 是基本變數， ${\displaystyle x_{j}}$是非基本變數。重寫方程，使整數部分位於等號左邊，小數部分位於等號右邊：

${\displaystyle 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 。因此不等式

${\displaystyle {\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 中如果 ${\displaystyle x_{i}}$ 不是整數，

${\displaystyle {\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}$

所以上方的不等式排除了基本可行解，並且是符合需求的一次切割。通過將新的鬆弛變數 ${\displaystyle x_{k}}$ 引入不等式中，新的約束得以加入到線性問題中：

${\displaystyle 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. Cutting planes in integer and mixed integer programming (PDF). Discrete Applied Mathematics. 2002, (123): 387–446 [2017-09-09]. （原始內容存檔 (PDF)於2022-03-02）.
• 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. [1] （頁面存檔備份，存於互聯網檔案館）
• Cornuéjols, Gérard (2007). Revival of the Gomory Cuts in the 1990s. Annals of Operations Research, Vol. 149 (2007), pp. 63–66. [2] （頁面存檔備份，存於互聯網檔案館）

外部連結

• "Integer Programming" Section 9.8 （頁面存檔備份，存於互聯網檔案館） Applied Mathematical Programming Chapter 9 Integer Programming (full text). Bradley, Hax, and Magnanti (Addison-Wesley, 1977)