分支定界

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

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

概述

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

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

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

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

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

通用格式

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

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

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

偽代碼

和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為子程序，必須基於具體問題進行設計。

改進

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