--- title: "Branch and bound — 分支定界法" source: "https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95" wiki: "systems-analysis.info/int" article: "Branch_and_bound_—_分支定界法" language: "zh" categories: - "Category:Chinese" - "Category:Operations research" - "Category:Optimization" revision_id: 819 wiki_created_at: 2026-09-06T22:39:17Z wiki_modified_at: 2026-09-06T22:39:17Z downloaded_at: 2026-09-07T22:42:32Z --- # Branch and bound — 分支定界法 **分支定界法**（英语：*Branch and Bound*，缩写为 **B&B** 或 **BnB**）是一种为求解离散优化和组合优化问题（特别是 NP-hard 问题）构建精确算法的通用范式^{[\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_note-en-wiki-bnb-1)}。该方法是一种定向枚举策略，其中所有可行解的集合被相继划分为子集（**分支**），并为每个子集计算目标函数值的估计（**界限**）。这些估计值允许丢弃（剪枝）那些显然不包含最优解的子集，从而显著缩小搜索空间^{[\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_note-ru-wiki-bnb-2)}。该方法由 A. H. Land 和 A. G. Doig 于1960年首次提出，用于解决整数规划问题^{[\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_note-land-doig-1960-3)}。从那时起，它已成为运筹学和计算机科学中最基本的方法之一。该方法的关键特点是其灵活性：它不是一个具体的算法，而是一个能够适应所解决问题结构的高级策略框架（framework）。 ## 方法的关键组成部分该方法基于三种基本操作，这些操作应用于以搜索树形式组织的解空间的子集。 - **分支**（英语：*Branching*）——是将当前可行解集 $S_{i}$ 递归地划分为几个更小的、通常不相交的子集 $S_{i1},S_{i2},\ldots,S_{ik}$ 的过程。每个这样的子集对应一个新的子问题，并在搜索树中表示为一个子节点。例如，在整数规划问题中，分支通常是根据在线性规划松弛解中取值为小数的变量进行的。 - **定界**（英语：*Bounding*）——为搜索树的每个节点（即每个子问题）计算目标函数值的估计。对于最小化问题，这是一个**下界**（*lower bound*），它是该子集中任何解的保证下限。这个界限通常通过求解原始子问题的*松弛*（relaxation）版本得到——这是一个简化版本，其中一些复杂的约束（例如，整数约束）被暂时忽略。最常用的是线性规划松弛（LP-relaxation）。 - **剪枝**（英语：*Pruning*）——是排除那些显然不可能包含最优解的节点（及其对应的整个子树）的过程。一个节点在以下情况之一被剪枝： 1. **按界剪枝**：当前节点的下界不优于（即对于最小化问题，大于或等于）当前找到的最佳可行解的值，这个最佳解被称为**记录值**（*incumbent*）。 2. **按可行性剪枝**：节点的松弛解对于原问题是可行的（例如，所有变量都是整数）。将此解与当前记录值进行比较，如果更优，则更新记录值。此时无需从此节点进一步分支。 3. **按无解剪枝**：与该节点对应的子问题没有可行解。 ## 通用算法分支定界法解决最小化问题的通用算法可以描述为以下步骤： 1. **初始化：**找到一个初始可行解（例如，使用启发式方法），并将其值设为初始上界（记录值）$U$。创建一个包含根节点（原始问题）的活动节点队列 $Q$。 2. **主循环：** 当队列 $Q$ 不为空时： - 根据搜索策略（例如，深度优先或最佳优先）从 $Q$ 中选择一个节点。 - 求解该节点的松弛问题，得到下界 $L$。 - 如果 $L \geq U$，则**剪枝**该节点。 - 如果松弛解对原问题可行，则更新记录值：$U\leftarrow L$。 - 如果节点未被剪枝且解不是可行解，则执行**分支**操作，将其划分为子节点，并将其添加到队列 $Q$ 中。 3. **终止：** 当队列 $Q$ 为空时，算法结束。与记录值 $U$ 对应的解即为全局最优解。 ## 关键属性与定理 - **正确性与收敛性：** 如果可行解集是有限的，并且分支过程是收敛的（即，在递归划分中，子集“收缩”到点），算法保证在有限步内找到全局最优解^{[\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_note-conitzer-duke-4)}。 - **搜索策略：** 算法的效率在很大程度上取决于选择下一个分支节点的策略（例如，深度优先搜索、广度优先搜索、最佳优先搜索）以及分支变量的选择。现代求解器通常使用混合策略^{[\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_note-maudet-danoy-2024-5)}。 ## 示例 - **整数规划问题**：该方法的经典应用。使用线性规划作为松弛。分支根据小数变量 $x_{j}$ 进行，创建两个带有附加约束 $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ 和 $x_{j} \geq \lceil x_{j}^{\ast}\rceil$ 的子问题。 - **旅行商问题**：解空间是图中所有可能的哈密顿回路。分支可以根据边（在路径中包含/排除某条边）进行。作为下界，可以使用更简单问题的解，例如分配问题或构建最小生成树^{[\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_note-little-1963-6)}。 ## 相关概念与应用 - **分支切割法**（*Branch-and-Cut*）：一种混合方法，将 B&B 与切割平面法相结合。在搜索树的每个节点，除了求解松弛问题外，还会生成额外的线性不等式（切割），以加强下界，从而更有效地剪枝。 - **回溯法**（*Backtracking*）：分支定界法可以看作是该算法在优化问题上的推广。 - **Alpha-beta 剪枝**：一个概念上的类似方法，用于博弈树中，以剪掉必败的分支。 ## 参考文献 1. [↑](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_ref-en-wiki-bnb_1-0) Wikipedia contributors. (2025). Branch and bound. In *Wikipedia, The Free Encyclopedia*. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound 2. [↑](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_ref-ru-wiki-bnb_2-0) Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ 3. [↑](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_ref-land-doig-1960_3-0) Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. *Econometrica*, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129 4. [↑](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_ref-conitzer-duke_4-0) Conitzer, V. (2008). *Solving (mixed) integer programs using branch and bound*. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf 5. [↑](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_ref-maudet-danoy-2024_5-0) Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. *arXiv preprint arXiv:2412.09444*. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444 6. [↑](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%E5%88%86%E6%94%AF%E5%AE%9A%E7%95%8C%E6%B3%95#cite_ref-little-1963_6-0) Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. *Operations Research*, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf