Branch and bound — 分支定界法

分支定界法（英语：Branch and Bound，缩写为 B&B 或 BnB）是一种为求解离散优化和组合优化问题（特别是 NP-hard 问题）构建精确算法的通用范式。该方法是一种定向枚举策略，其中所有可行解的集合被相继划分为子集（分支），并为每个子集计算目标函数值的估计（界限）。这些估计值允许丢弃（剪枝）那些显然不包含最优解的子集，从而显著缩小搜索空间。

该方法由 A. H. Land 和 A. G. Doig 于1960年首次提出，用于解决整数规划问题。从那时起，它已成为运筹学和计算机科学中最基本的方法之一。该方法的关键特点是其灵活性：它不是一个具体的算法，而是一个能够适应所解决问题结构的高级策略框架（framework）。

方法的关键组成部分

该方法基于三种基本操作，这些操作应用于以搜索树形式组织的解空间的子集。

• 分支（英语：Branching）——是将当前可行解集 $S_i$ 递归地划分为几个更小的、通常不相交的子集 $S_{i1},S_{i2},\dots ,S_{ik}$ 的过程。每个这样的子集对应一个新的子问题，并在搜索树中表示为一个子节点。例如，在整数规划问题中，分支通常是根据在线性规划松弛解中取值为小数的变量进行的。

• 定界（英语：Bounding）——为搜索树的每个节点（即每个子问题）计算目标函数值的估计。对于最小化问题，这是一个下界（lower bound），它是该子集中任何解的保证下限。这个界限通常通过求解原始子问题的松弛（relaxation）版本得到——这是一个简化版本，其中一些复杂的约束（例如，整数约束）被暂时忽略。最常用的是线性规划松弛（LP-relaxation）。

• 剪枝（英语：Pruning）——是排除那些显然不可能包含最优解的节点（及其对应的整个子树）的过程。一个节点在以下情况之一被剪枝：

1. 按界剪枝：当前节点的下界不优于（即对于最小化问题，大于或等于）当前找到的最佳可行解的值，这个最佳解被称为记录值（incumbent）。
2. 按可行性剪枝：节点的松弛解对于原问题是可行的（例如，所有变量都是整数）。将此解与当前记录值进行比较，如果更优，则更新记录值。此时无需从此节点进一步分支。
3. 按无解剪枝：与该节点对应的子问题没有可行解。

通用算法

分支定界法解决最小化问题的通用算法可以描述为以下步骤：

1. 初始化：找到一个初始可行解（例如，使用启发式方法），并将其值设为初始上界（记录值）$U$。创建一个包含根节点（原始问题）的活动节点队列 $Q$。
2. 主循环： 当队列 $Q$ 不为空时：
   • 根据搜索策略（例如，深度优先或最佳优先）从 $Q$ 中选择一个节点。
   • 求解该节点的松弛问题，得到下界 $L$。
   • 如果 $L\ge U$，则剪枝该节点。
   • 如果松弛解对原问题可行，则更新记录值：$U\leftarrow L$。
   • 如果节点未被剪枝且解不是可行解，则执行分支操作，将其划分为子节点，并将其添加到队列 $Q$ 中。
3. 终止： 当队列 $Q$ 为空时，算法结束。与记录值 $U$ 对应的解即为全局最优解。

关键属性与定理

• 正确性与收敛性： 如果可行解集是有限的，并且分支过程是收敛的（即，在递归划分中，子集“收缩”到点），算法保证在有限步内找到全局最优解。
• 搜索策略： 算法的效率在很大程度上取决于选择下一个分支节点的策略（例如，深度优先搜索、广度优先搜索、最佳优先搜索）以及分支变量的选择。现代求解器通常使用混合策略。

示例

• 整数规划问题：该方法的经典应用。使用线性规划作为松弛。分支根据小数变量 $x_j$ 进行，创建两个带有附加约束 $x_j\le \lfloor x_j^{*}\rfloor$ 和 $x_j\ge \lceil x_j^{*}\rceil$ 的子问题。
• 旅行商问题：解空间是图中所有可能的哈密顿回路。分支可以根据边（在路径中包含/排除某条边）进行。作为下界，可以使用更简单问题的解，例如分配问题或构建最小生成树。

相关概念与应用

• 分支切割法（Branch-and-Cut）：一种混合方法，将 B&B 与切割平面法相结合。在搜索树的每个节点，除了求解松弛问题外，还会生成额外的线性不等式（切割），以加强下界，从而更有效地剪枝。
• 回溯法（Backtracking）：分支定界法可以看作是该算法在优化问题上的推广。
• Alpha-beta 剪枝：一个概念上的类似方法，用于博弈树中，以剪掉必败的分支。