分支切割法

分支切割法是用於解決整數線性問題（ILPs），即部分或全部未知數為整數值的線性規劃（LP）的問題的組合優化方法。該方法在分支定界法的基礎上，使用切割平面以收緊線性規劃鬆弛。如果切割平面僅用來收緊初始的 LP 鬆弛，則改稱為切割分支法。

算法描述

以下假設 ILP 問題為最大化問題。

該方法首先使用單純形法解決無整數約束的線性問題。獲得最優解後，如果有約束為整數的變量取了非整數值，該算法會使用切割平面法以尋找進一步的線性約束：所有可行的整數點滿足該約束，但目前的最優解不滿足該約束。隨後這些約束不等式可以加入線性問題中，使得下次求解可以獲得「更接近整數」的結果。

在此基礎上，算法使用分支定界法，將該問題分割為多個（通常為兩個）子問題。隨後使用單純形法求解新的子問題，重複該過程。在分支定界的過程中，LP 鬆弛問題的非整數解為解的上限，整數解為解的下限。如果一個子問題的上限低於當前的全局下限，則可以除去該子問題。此外，在求解 LP 鬆弛問題時，可能產生其他切割平面。這些平面既可能是全局切割，即適用於所有可行的整數解的切割；或局部切割，即適用於當前分支定界子樹下所有滿足邊界約束的解的切割。

算法概括如下：

1. 將原 ILP 問題加入活躍問題列表 $L$ 中。
2. 取 $x^{*}={\text{null}}$ , $v^{*}=-\infty$。
3. 當 $L$ 非空時
   1. 從 $L$ 中選擇一個問題，並將其移出 L 。
   2. 解該問題的 LP 鬆弛問題。
   3. 如果該解不可行，返回第 3 步重新開始。如果該解可行，獲得解 $x$ 及目標函數值 $v$。
   4. 如果 $v\leq v^{*}$, 返回第 3 步。
   5. 如果 $x$ 為整數，令 $v^{*}\leftarrow v,x^{*}\leftarrow x$ ，返回第 3 步。
   6. 如有需要，尋找使 $x$ 不滿足約束的切割平面。如果能找到相應平面，則將其加入 LP 鬆弛問題中，返回第 3.2 步。
   7. 進行分支，使得原問題分為可行空間更小的子問題。將這些問題加入 $L$ 中，返回第 3 步。
4. 返回 $x^{*}$ 值。

分支策略

分支策略是分支切割算法中的重要一步。在這一步中，可以使用多種啟發式分支策略。下述分支策略都包含在變量上分支。在變量上分支的大致過程為：如果變量 $x_{i}$ 在當前的 LP 鬆弛問題的最優解中為分數 $x_{i}'$ ，則向鬆弛問題中加入約束 $x_{i}\leq \lfloor x_{i}'\rfloor$ ， $x_{i}\geq \lceil x_{i}'\rceil$ 。

最不可行分支

該策略優先選擇小數部分最接近 0.5 的變量。

偽成本分支

該策略的基本思想是當變量 $x_{i}$ 被選作分支變量時，追蹤目標函數的變化。基於過去的變化情況，該策略會選擇預計對目標函數產生最大變化的變量作為分支變量。注意，在最初分支時，只有幾個變量進行過分支，該策略會面臨所需信息不足的情況。

強健分支

該策略在實際分支前將對變量進行測試，以確定哪個變量對目標函數的變化影響最大。完全強健分支會測試所有候選變量，計算成本很高。可以通過只考慮一部分候選變量，並不完全解出所有對應的 LP 鬆弛，來降低計算成本。

除了以上幾種策略外，還存在大量其他的分支策略，比如偽成本分支所需的信息不足時先採用強壯分支，在獲得足夠的分支歷史後切換到偽成本分支。

外部連結

• Mixed Integer Programming
• SCIP （頁面存檔備份，存於網際網路檔案館） Branch-cut-and-price 框架，及混合整數規劃求解器
• ABACUS - A Branch-And-CUt System 開源軟件
• COIN-OR Cbc 開源軟件