分支切割法
![]() | 此條目內容疑欠準確,有待查證。 (2017年9月9日) |
此條目翻譯品質不佳。 (2017年9月9日) |
分支切割法[1]是用於解決整數線性問題(ILPs),即部分或全部未知數為整數值的線性規劃(LP)的問題的組合優化方法。[2]該方法在分支定界法的基礎上,使用切割平面以收緊線性規劃鬆弛。如果切割平面僅用來收緊初始的 LP 鬆弛,則改稱為切割分支法。
算法描述
[編輯]以下假設 ILP 問題為最大化問題。
該方法首先使用單純形法解決無整數約束的線性問題。獲得最優解後,如果有約束為整數的變量取了非整數值,該算法會使用切割平面法以尋找進一步的線性約束:所有可行的整數點滿足該約束,但目前的最優解不滿足該約束。隨後這些約束不等式可以加入線性問題中,使得下次求解可以獲得「更接近整數」的結果。
在此基礎上,算法使用分支定界法,將該問題分割為多個(通常為兩個)子問題。隨後使用單純形法求解新的子問題,重複該過程。在分支定界的過程中,LP 鬆弛問題的非整數解為解的上限,整數解為解的下限。如果一個子問題的上限低於當前的全局下限,則可以除去該子問題。此外,在求解 LP 鬆弛問題時,可能產生其他切割平面。這些平面既可能是全局切割,即適用於所有可行的整數解的切割;或局部切割,即適用於當前分支定界子樹下所有滿足邊界約束的解的切割。
算法概括如下:
- 將原 ILP 問題加入活躍問題列表 中。
- 取 , 。
- 當 非空時
- 從 中選擇一個問題,並將其移出 L 。
- 解該問題的 LP 鬆弛問題。
- 如果該解不可行,返回第 3 步重新開始。如果該解可行,獲得解 及目標函數值 。
- 如果 , 返回第 3 步。
- 如果 為整數,令 ,返回第 3 步。
- 如有需要,尋找使 不滿足約束的切割平面。如果能找到相應平面,則將其加入 LP 鬆弛問題中,返回第 3.2 步。
- 進行分支,使得原問題分為可行空間更小的子問題。將這些問題加入 中,返回第 3 步。
- 返回 值。
分支策略
[編輯]分支策略是分支切割算法中的重要一步。在這一步中,可以使用多種啟發式分支策略。下述分支策略都包含在變量上分支。[3]在變量上分支的大致過程為:如果變量 在當前的 LP 鬆弛問題的最優解中為分數 ,則向鬆弛問題中加入約束 , 。
最不可行分支
[編輯]該策略優先選擇小數部分最接近 0.5 的變量。
偽成本分支
[編輯]該策略的基本思想是當變量 被選作分支變量時,追蹤目標函數的變化。基於過去的變化情況,該策略會選擇預計對目標函數產生最大變化的變量作為分支變量。注意,在最初分支時,只有幾個變量進行過分支,該策略會面臨所需信息不足的情況。
強健分支
[編輯]該策略在實際分支前將對變量進行測試,以確定哪個變量對目標函數的變化影響最大。完全強健分支會測試所有候選變量,計算成本很高。可以通過只考慮一部分候選變量,並不完全解出所有對應的 LP 鬆弛,來降低計算成本。
除了以上幾種策略外,還存在大量其他的分支策略,比如偽成本分支所需的信息不足時先採用強壯分支,在獲得足夠的分支歷史後切換到偽成本分支。
外部連結
[編輯]- Mixed Integer Programming
- SCIP (頁面存檔備份,存於網際網路檔案館) Branch-cut-and-price 框架,及混合整數規劃求解器
- ABACUS - A Branch-And-CUt System 開源軟件
- COIN-OR Cbc 開源軟件
參考文獻
[編輯]- ^ Padberg, M. & Rinaldi, G. A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. Siam Review. 1991: 60–100. doi:10.1137/1033004.
- ^ John E., Mitchell. Branch-and-Cut Algorithms for Combinatorial Optimization Problems. Handbook of Applied Optimization. 2002: 65–77.
- ^ Achterberg, Tobias; Koch, Thorsten; Martin, Alexander. Branching rules revisited. Operations Research Letters: 42–54. [2017-09-08]. doi:10.1016/j.orl.2004.04.002. (原始內容存檔於2019-06-07).