分枝界限法

出自 MBA智库百科(https://wiki.mbalib.com/)

分枝界限法(Branch and Bound Method)

　分枝界限法是由三棲學者查理德·卡普（Richard M.Karp）在20世紀60年代發明，成功求解含有65個城市的旅行商問題，創當時的記錄。“分枝界限法”把問題的可行解展開如樹的分枝，再經由各個分枝中尋找最佳解^[1]。

　　分枝界限法也能夠使用在混合整數規劃問題上，其為一種系統化的解法，以一般線性規劃之單形法解得最佳解後，將非整數值之決策變數分割成為最接近的兩個整數，分列條件，加入原問題中，形成兩個子問題(或分枝)分別求解，如此便可求得目標函數值的上限（上界）或下限（下界），從其中尋得最佳解^[2]。

　　1、基本思想

　　分枝定界法是一個用途十分廣泛的演算法，運用這種演算法的技巧性很強，不同類型的問題解法也各不相同。分支定界法的基本思想是對有約束條件的最優化問題的所有可行解（數目有限）空間進行搜索。該演算法在具體執行時，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），併為每個子集內的解的值計算一個下界或上界（稱為定界）。在每次分支後，對凡是界限超出已知可行解值那些子集不再做進一步分支。這樣，解的許多子集（即搜索樹上的許多結點）就可以不予考慮了，從而縮小了搜索範圍。這一過程一直進行到找出可行解為止，該可行解的值不大於任何子集的界限。因此這種演算法一般可以求得最優解。

　　將問題分枝為子問題並對這些子問題定界的步驟稱為分枝定界法。

　　2、分枝節點的選擇

　　對搜索樹上的某些點必須作出分枝決策，即凡是界限小於迄今為止所有可行解最小下界的任何子集（節點），都有可能作為分枝的選擇對象（對求最小值問題而言）。怎樣選擇搜索樹上的節點作為下次分枝的節點呢？有兩個原則：

　　1）從最小下界分枝（隊列式FIFO分枝限界法）：每次算完界限後，把搜索樹上當前所有葉節點的界限進行比較。找出限界最小的節點，此結點即為下次分枝的結點。

• 優點：檢查子問題較少，能較快地求得最佳解；
• 缺點：要存儲很多葉節點的界限及對應的耗費矩陣，花費很多記憶體空間。

　　2）從最新產生的最小下界分枝（優先隊列式分枝限界法）：從最新產生的各子集中選擇具有最小的下界的結點進行分枝。

優點：節省了空間； 缺點：需要較多的分枝運算，耗費的時間較多。

　　這兩個原則更進一步說明瞭，在演算法設計中的時空轉換概念。

　　分枝定界法已經成功地應用於求解整數規劃問題、生產進度表問題、貨郎擔問題、選址問題、背包問題以及可行解的數目為有限的許多其它問題。對於不同的問題，分枝與界限的步驟和內容可能不同，但基本原理是一樣的。

　　分枝界限法是組合優化問題的有效求解方法，其步驟如下所述：

　　步驟一：如果問題的目標為最小化，則設定目前最優解的值Z=∞

　　步驟二：根據分枝法則（Branching rule），從尚未被洞悉（Fathomed）節點（局部解）中選擇一個節點，併在此節點的下一階層中分為幾個新的節點。

　　步驟三：計算每一個新分枝出來的節點的下限值（Lower bound，LB）

　　步驟四：對每一節點進行洞悉條件測試，若節點滿足以下任意一個條件，則此節點可洞悉而不再被考慮：

• 此節點的下限值大於等於Z值。
• 已找到在此節點中，具最小下限值的可行解；若此條件成立，則需比較此可行解與Z值，若前者較小，則需更新Z值，以此為可行解的值。
• 此節點不可能包含可行解。

　　步驟五：判斷是否仍有尚未被洞悉的節點，如果有，則進行步驟二，如果已無尚未被洞悉的節點，則演算停止，並得到最優解。

　　Kolen等曾利用此方法求解含時間窗約束的車輛巡迴問題，其實驗的節點數範圍為6-15。當節點數為6時，電腦演算所花費的時間大約1分鐘（電腦型為VAZ11/785），當節點數擴大至12時，電腦有記憶體不足的現象產生，所以分枝定界法比較適用於求解小型問題。Held和Karp指出分枝定界法的求解效率，與其界限設定的寬緊有極大的關係。

　　1、型推銷員問題

　　設有5個城v₁,v₂,v₃,v₄,v₅ ,從某一城市出發，遍歷各城市一次且僅一次，最後返回原地，求最短路徑。其費用矩陣如下：

　　將矩陣D對角線以上的元素從小到大排列為：

　　d₁₃,d₁₅,d₂₄,d₄₅,d₃₄,d₃₅KKKK

　　取最小的5個求和得：d₁₃ + d₁₅ + d₂₄ + d₄₅ = 14

　　用表示，要構成一個迴路，所以每個頂點的下標在迴路的所有邊中各出現兩次。（1）中顯然5出現了3次，若用d₃₅代替d₁5則d₁₃ + d₃₅ + d₂₄ + d₂₅ + d₄₅ = 21即

　　搜索過程可以表示如下圖：

　　圖（2）的下界為21，圖（3）的下界為20，都大於19故沒有進一步搜索的價值，因此（5）為最佳路徑：

　　2、型推銷員問題

　　D = (d_ij)n ^* n即。不妨把D看成旅費，即從v_i到v_j的旅費與v_j到v_i不一樣。

　　對D的每行減去該行的最小元素，或每列減去該列的最小元素，得一新矩陣，使得每行每列至少都有一個0元素。

　　第一列和第三列沒有為0的元素，所以第一列和第三列分別減去其最小元素1和3得：

　　由於從任一v_i出發一次，進入v_i也是一次，所以問題等價於求 的最佳路徑，下標45是估計的界，即旅費起碼為45單位（每個點出發都去最小值）。

　　由於矩陣D第一行第四列元素為0，故從v₁出發的路徑應選擇v₁ − − v₄，為了排除v₁出發進入其他點和從其他點進入v₄的可能，並封鎖v₄到v₁的路徑，在矩陣中除去第一行和第四列，並將第四列第一行元素15改為∞。得：

　　類似的從v₂出的路徑應選v₂ − − v₅，消第v₂行和第v₅列，並將第v₅行第v₂列元素改為∞得：

　　這時第二行沒有0元素，減去最小元素3得： 　　

　　搜索過程如下圖：

　　最後得到最佳路徑為：

　　1、演算法優點：可以求得最優解、平均速度快。

　　因為從最小下界分支，每次算完限界後，把搜索樹上當前所有的葉子結點的限界進行比較，找出限界最小的結點，此結點即為下次分支的結點。這種決策的優點是檢查子問題較少，能較快的求得最佳解。

　　2、缺點：要存儲很多葉子結點的限界和對應的耗費矩陣。花費很多記憶體空間。

　　存在的問題：分支定界法可應用於大量組合優化問題。其關鍵技術在於各結點權值如何估計，可以說一個分支定界求解方法的效率基本上由值界方法決定，若界估計不好，在極端情況下將與窮舉搜索沒多大區別。