基本介紹
- 中文名：切割平面法
- 外文名：Cutting-plane method
簡介,Gomory 切割,凸最佳化,另見,
簡介
MILP 的切割平面法通過將整數問題線性鬆弛為非整數線性問題，並對其進行求解，來求解 MILP 問題。線性規劃理論說明，在溫和的假定下（如果線性規劃存在最優解，並且可行域不包含一條線），總存在一個極值點或頂點是最優的。 檢驗所獲的最優解是否為整數解。如否，則必然存在一線性不等式將最優點和真可行集的凸包分離。找到這樣的不等式是分離問題，而這樣的不等式就是切割。 切割可以被加入到被鬆弛的線性規劃中，使得當前的非整數解對鬆弛不再可行。該過程不斷重複，直到找到最優整數解。
用於普遍的凸連續最佳化和變體的切割平面法有不同的名稱： Kelley 法， Kelley-Cheney-Goldstein 法和捆綁法。它們常用於不可微的凸最小化問題。對於這類問題，通常的可微最佳化的梯度法無法使用，而使用這些方法可以高效地得到凸目標函式及其次梯度。這種情況最常出現在雙拉格朗日函式的凹最佳化中。另一種常見情形是 Dantzig-Wolfe 分解套用於結構最佳化問題中，這類問題通常有含有指數級變數的表達式。通過延遲列生成法按需生成這些變數等同於在對應的對偶問題上切割平面。
Gomory 切割
切割平面法由 Ralph Gomory 在 19 世紀 50 年代提出，用於解決整數規劃和混合整數規劃問題。然而，當時的大多數專家，包括 Gomory 自己都認為由於數值上的不穩定性，這種方法沒有實際運用價值；同時由於求解過程中需要進行過多輪的切割，該方法可能是無效的。而在 19 世紀 90 年代中期，發現切割平面法與分支定界法結合（稱作分支切割法）時效率很高，並且能有效克服數值不穩定性。現在，所有的商用 MILP 求解器都或多或少地使用了 Gomory 切割。Gomory 切割可通過單一單純形表格生成，相比於其他計算成本高昂、甚至分離為 NP-困難的其他切割法來說十分高效。在其他 MILP 的普遍切割法中，提升和投影割平面法明顯優於 Gomory 切割。
設一整數規劃問題被表達為其標準形式：
該方法首先將
為整數的約束進行鬆弛，並求解相應的線性規劃問題，得出基本可行解。在幾何層面上，該解為含有所有可行解的凸多胞形的一個頂點。如果該頂點不是整數點，則該方法將凸多胞形分為兩部分，一部分含有該頂點的超平面，另一部分含有所有整數解。該超平面隨即作為額外的線性約束加入到問題中，構成修正的線性問題，以排除前一步發現的頂點。隨後求解新的線性問題，重複這一過程，直到發現整數解。
使用單純形法求解線性問題會產生一組如下形式的方程
其中 是基本變數，
是非基本變數。重寫方程，使整數部分位於等號左邊，小數部分位於等號右邊：
對於任意位於可行域的整數點，等號右邊小於 1 ，而等號左邊為整數，因此兩邊共同的取值必然小於或等於 0 。因此不等式
對於可行域內的所有整數點必須成立。此外，在基本可行解中，非基本變數都為 0 ，而且基本可行解 x 中如果{\displaystyle x_{i}}不是整數，
所以上方的不等式排除了基本可行解，並且是符合需求的一次切割。通過將新的鬆弛變數 
引入不等式中，新的約束得以加入到線性問題中：
凸最佳化
切割平面法也適用於非線性規劃。 其基本原理是通過封閉半空間的有限集估算非線性（凸）問題的可行域，並對一系列的線性問題估算進行求解。
另見
- Benders 分解法
- 分支切割法
- Dantzig-Wolfe 分解
