分支定界

分支定界（英語：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.