分支定界

分支定界（英語：Branch and bound，BB）是用於離散最佳化、組合最佳化以及數學最佳化問題的演算法設計範式。分支定界演算法可以視為一種對可行解進行窮舉的演算法，但是和窮舉法所不同的是，分支定界演算法在對某一分支進行檢索之前會先算出該分支的上界或下界，如果界限不比目前最佳解更好，那麼該分支就會被捨棄，從而節約了大量的時間。分支定界演算法非常依賴合適的上界或下界，如果無法找到合適的界限，該演算法將會退化為窮舉法。

該方法最初是由阿爾薩·蘭德和艾莉森·哈考特在1960年由英國石油公司贊助的倫敦經濟學院進行離散規劃研究時提出的，^[1]目前已成為解決NP困難最佳化問題最常用的工具。^[2]「分支定界」一詞最早出現在解決旅行推銷員問題的時候。^[3][4]

概述

分支定界法的目的是從可行解集合${\displaystyle S}$中選出一個解${\displaystyle x}$，使得目標函數${\displaystyle f(x)}$最大化或最小化。其中集合${\displaystyle S}$被稱為搜尋空間或可行區域。本節所有的最佳化問題均可視為對${\displaystyle f(x)}$進行最小化，因為對${\displaystyle f(x)}$進行最大化問題本質上還是對${\displaystyle g(x)=-f(x)}$進行最小化。分支定界法需要遵循以下兩個原則：

• 先是將搜尋空間通過遞歸的手段分成多個子空間，在每個子空間對${\displaystyle f(x)}$進行最小化，這種分割方式就是分支。
• 如果只有分支那麼這種方法就成為了暴力搜尋法，運算量將會非常龐大。為了提升演算法的效能，需要對每個分支進行下界計算，對於那些下界已經超過目前最佳解的分支，需要進行剪枝操作。

為了將這些原則轉化為問題的具體演算法，我們需要將這些候選解轉化為合適的數據結構，這樣的表示方式被稱為問題的實例。我們用${\displaystyle S_{I}}$表示實例${\displaystyle I}$的候選解集，實例表示必須有如下三個操作:

• ${\displaystyle branch(I)}$：產生兩個或多個實例，每個實例為${\displaystyle S_{I}}$的一個子集。（通常來講，每個子集都是互不相交的，這是為了避免每個候選解被多次訪問從而浪費時間，但有時也會有例外。${\displaystyle S_{I}}$的最佳解必然會出現在它的一個或多個子集中。^[5]）
• ${\displaystyle bound(I)}$：計算實例${\displaystyle I}$中所有候選解所對應的目標函數值的下界，滿足對於任意${\displaystyle x\in S_{I}}$，${\displaystyle bound(I)\leq f(x)}$。
• ${\displaystyle solution(I)}$：確定${\displaystyle I}$是否表示單個候選解。（如果不是，接下來可以從${\displaystyle S_{I}}$中回傳一些可行的解再進一步進行分支定界的操作。^[5]）如果${\displaystyle solution(I)}$回傳了一個解，那麼${\displaystyle f(solution(I))}$提供了整個可行解空間中最佳目標函數的上界。

通過使用這些操作，分支定界演算法在分支操作形成的實例樹中執行自頂向下遞歸搜尋。在訪問實例${\displaystyle I}$時，我們不妨先檢查${\displaystyle bound(I)}$，如果${\displaystyle bound(I)}$已經大於目前所找到的上界，我們就直接丟棄該實例。為了實現這一步驟，我們需要設定一個全域變數，用於記錄目前為止所檢查的所有實例中看到的最小上界。

通用格式

下面是最小化任意目標函數${\displaystyle f}$的通用分支定界演算法框架。^[2]要從中得到一個演算法，我們需要一個邊界函數，用來計算函數${\displaystyle f}$在搜尋樹節點上的下界，以及一個基於特定問題的分支規則。本文提出的通用演算法是一個高階函數。

1. 首先使用啟發法找出一個最佳化問題的解${\displaystyle x_{h}}$,並儲存數值${\displaystyle B=f(x_{h})}$。（如果無法通過啟發法找到解，則設B的值為無窮大）B表示到目前為止找到的最佳解，並把它作為候選解的上界。
2. 初始化一個佇列，用於儲存在不進行變數分配時所得到的局部解。
3. 執行如下迴圈直至佇列被清空：
   1. 從佇列中取出節點${\displaystyle N}$
   2. 如果節點${\displaystyle N}$代表單一的候選解${\displaystyle x}$且滿足${\displaystyle f(x)<B}$，那麼我們就可以說${\displaystyle x}$為目前所找到的最佳解，令${\displaystyle B}$←${\displaystyle f(x)}$。
   3. 反之，節點${\displaystyle N}$產生新的分支節點${\displaystyle N_{i}}$，對於這些新產生的節點：
      1. 如果${\displaystyle bound(N_{i})>B}$，則捨棄該節點，因為最佳解不可能出現在這個節點裏。
      2. 反之，將節點${\displaystyle N_{i}}$存入佇列。

在這一演算法中，佇列也可以替換為其他的數據結構。在使用遵循先進先出原則的佇列時，該演算法屬於廣度優先搜尋。反之如果使用遵循先進後出的堆疊儲存節點，該演算法就成為了深度優先搜尋。當然，也可以使用優先佇列對所有的節點的下界進行排序，進一步提升效率。^[2]採用這種演算法的例子是戴克斯特拉演算法及其衍生的A*搜尋演算法。當無法通過啟發法生成初始解時，建議使用深度優先演算法的變體，因為它可以快速生成完整解，從而得到整個問題的上界。^[6]

偽代碼

和C++語言相似的偽代碼如下：

// C++-like implementation of branch and bound, 
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
    CombinatorialProblem problem, 
    ObjectiveFunction objective_function /*f*/,
    BoundingFunction lower_bound_function /*bound*/) 
{
    // Step 1 above
    double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
    CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
    problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
    CombinatorialSolution current_optimum = heuristic_solution;
    // Step 2 above
    queue<CandidateSolutionTree> candidate_queue;
    // problem-specific queue initialization
    candidate_queue = populate_candidates(problem);
    while (!candidate_queue.empty()) { // Step 3 above
        // Step 3.1
        CandidateSolutionTree node = candidate_queue.pop();
        // "node" represents N above
        if (node.represents_single_candidate()) { // Step 3.2
            if (objective_function(node.candidate()) < problem_upper_bound) {
                current_optimum = node.candidate();
                problem_upper_bound = objective_function(current_optimum);
            }
            // else, node is a single candidate which is not optimum
        }
        else { // Step 3.3: node represents a branch of candidate solutions
            // "child_branch" represents N_i above
            for (auto&& child_branch : node.candidate_nodes) {
                if (lower_bound_function(child_branch) <= problem_upper_bound) {
                    candidate_queue.enqueue(child_branch); // Step 3.3.2
                }
                // otherwise, bound(N_i) > B so we prune the branch; step 3.3.1
            }
        }
    }
    return current_optimum;
}

在上述偽代碼中，函數heuristic_solve和populate_candidates為子程式，必須基於具體問題進行設計。

改進

當${\displaystyle \mathbf {x} }$為空間處於${\displaystyle \mathbb {R} ^{n}}$的向量時，分支定界演算法可以與區間分析^[7]和間隔承包商技術相結合，以提供全域最小包絡值的保證。^[8][9]

參考文獻

1. Land, A. H.; Doig, A. G. An Automatic Method of Solving Discrete Programming Problems. Econometrica. 1960, 28 (3): 497–520 [2022-10-16]. ISSN 0012-9682. doi:10.2307/1910129. （原始內容存檔於2022-12-01）.
2. Clausen, Jens. Branch and Bound Algorithms—Principles and Examples (PDF) (技術報告). University of Copenhagen. 1999 [2014-08-13]. （原始內容 (PDF)存檔於2015-09-23）.
3. Little, John D. C.; Murty, Katta G.; Sweeney, Dura W.; Karel, Caroline. An algorithm for the traveling salesman problem (PDF). Operations Research. 1963, 11 (6): 972–989 [2022-03-03]. doi:10.1287/opre.11.6.972. hdl:1721.1/46828 . （原始內容存檔 (PDF)於2022-01-20）.
4. Balas, Egon; Toth, Paolo. Branch and Bound Methods for the Traveling Salesman Problem:. 1983-03-01 [2022-10-16]. doi:10.21236/ada126957. （原始內容存檔於2022-10-17）.
5. Bader, David A.; Hart, William E.; Phillips, Cynthia A. Parallel Algorithm Design for Branch and Bound (PDF). Greenberg, H. J. (編). Tutorials on Emerging Methodologies and Applications in Operations Research. Kluwer Academic Press. 2004 [2015-09-16]. （原始內容 (PDF)存檔於2017-08-13）.
6. Mehlhorn, Kurt; Sanders, Peter. Algorithms and Data Structures: The Basic Toolbox (PDF). Springer. 2008: 249 [2022-03-04]. （原始內容存檔 (PDF)於2018-06-19）.
7. Moore, R. E. Interval Analysis. Englewood Cliff, New Jersey: Prentice-Hall. 1966. ISBN 0-13-476853-1.
8. Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. Applied Interval Analysis. Berlin: Springer. 2001. ISBN 1-85233-219-0.
9. Hansen, E.R. Global Optimization using Interval Analysis. New York: Marcel Dekker. 1992.