分支定界法

分支定界法 (Branch and Bound)

分支定界法（Branch and Bound）是一种用于求解整数规划和组合优化问题的精确算法框架。其核心思想是将原问题的可行域系统地分割为若干较小的子问题（分支），对每个子问题计算目标函数最优值的界（定界），并利用这些界来剪除不可能包含最优解的子问题（剪枝），从而避免对整个可行域的穷举搜索。该方法由Land和Doig于1960年首次提出，最初针对整数线性规划问题，随后被推广至旅行商问题、背包问题、最大割问题、调度问题和设施选址问题等广泛的NP-难组合优化领域。尽管最坏情形下的时间复杂度仍为指数级，分支定界法凭借有效的剪枝策略和线性规划松弛的结合，在实践中对中等规模的问题通常能在合理时间内获得可证明的最优解，因此成为现代商业求解器（如CPLEX、Gurobi、SCIP）的核心算法组件。

算法框架

分支定界法以一棵搜索树（Branch-and-Bound Tree）组织计算。根节点代表原问题 $P_0$，每一个子节点对应一个通过添加约束而缩小的子问题 $P_k$。算法维护两个关键量：全局上界 $UB$（对于最小化问题而言）和每个待处理节点 $k$ 的下界 $LB_k$。搜索树的每个节点经历以下步骤：

1. 选择：从未处理的活跃节点列表中按某种策略（深度优先、广度优先或最佳下界优先）选取一个节点 $P_k$。
2. 定界：求解 $P_k$ 的松弛问题（通常是线性规划松弛，即暂时忽略整数约束），获得该节点的下界 $LB_k$。
3. 剪枝：若 $LB_k \geq UB$，则此节点可被永久丢弃（剪枝），因为其所有后代解都不可能优于当前已知的最好可行解。此外，若松弛问题不可行，节点亦被丢弃。若松弛解恰满足整数约束，则更新 $UB = \min(UB, OBJ_k)$ 并记录该解为当前最优。
4. 分支：若节点未被剪枝且松弛解不满足整数性要求，则选择一个不满足整数约束的变量 $x_j$（其松弛值为 $x_j^*$ 且 $x_j^* \notin \mathbb{Z}$），生成两个子节点，分别添加约束 $x_j \leq \lfloor x_j^* \rfloor$ 和 $x_j \geq \lceil x_j^* \rceil$，将子节点加入活跃列表。

算法终止时 $UB$ 即为全局最优值，对应的可行解为最优解。若活跃节点列表耗尽而 $UB$ 未更新，则问题不可行。

定界：LP松弛与对偶界

分支定界法效率的关键在于定界的质量——下界越紧，剪枝越早越有力。对整数线性规划 $\min \{\mathbf{c}^\top \mathbf{x} \mid \mathbf{Ax} \leq \mathbf{b}, \mathbf{x} \in \mathbb{Z}^n_+\}$，最常用的松弛是线性规划松弛（LP Relaxation），直接去除整数约束，得 $\min \{\mathbf{c}^\top \mathbf{x} \mid \mathbf{Ax} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}\}$。LP松弛提供有效下界：$z_{LP} \leq z_{IP}$，且可在多项式时间（内点法或单纯形法）内求解。

对于特定结构的整数规划，还可采用拉格朗日松弛：将部分难约束以惩罚项形式移入目标函数，获得更紧的下界。例如，对设施选址问题，松弛需求分配约束可得到可分解的子问题。对偶理论确保拉格朗日对偶界不弱于LP松弛界，且在整数性导致的对偶间隙较小的结构上表现尤为出色。

分支策略

分支变量的选择直接影响搜索树的规模和算法的收敛速度。常用策略包括：

• 最大分数部分法（Most Fractional）：选择松弛解中最接近0.5的变量，即 $\arg\max_j \min(x_j^* - \lfloor x_j^*\rfloor, \lceil x_j^*\rceil - x_j^*)$，直觉是离整数最远的变量最具"纠正"空间。
• 伪费用法（Pseudocost Branching）：基于历史信息，估计每个变量向上和向下分支对目标函数值的"单位变化"，选择预估改进量最大的变量。
• 强分支（Strong Branching）：对候选变量实际求解两个子节点的LP松弛，选择使下界提升最大的变量。虽然单步代价高，但能显著缩小搜索树，在困难实例中常优于其他策略。

现代求解器通常采用混合策略——在搜索树顶部使用强分支以快速提升全局下界，在深层切换到伪费用法以控制单节点求解成本。

剪枝条件与最优性证明

节点 $P_k$ 被剪枝（fathomed）的充分条件有三：

1. 下界剪枝：$LB_k \geq UB$，该节点的最优解不可能击败当前最佳可行解。
2. 不可行剪枝：$P_k$ 的松弛问题无可行解，则原整数子问题亦无可行解。
3. 整数可行剪枝：松弛解满足所有整数约束，则该节点已获得一个可行解，更新 $UB$ 后无需再分支。

当活跃节点列表为空时，算法终止。若 $UB$ 有限，当前记录的最优解即为全局最优；若 $UB$ 仍为 $+\infty$，则原问题不可行。分支定界法由此提供了最优性的严格数学证明，这是其区别于启发式算法（如遗传算法、模拟退火）的根本优势。

与割平面法的融合：分支切割法

分支定界法常与割平面法结合，形成分支切割法（Branch and Cut）。在每个节点求解LP松弛后，迭代添加割平面（Gomory小数割、覆盖不等式、团不等式等）以割除非整数极点，收紧LP松弛的下界。一旦无法生成有效的割或割的边际收益递减，再转向分支。这种融合大幅提升了纯分支定界法的效率——现代MILP求解器（Gurobi、CPLEX、SCIP）均以分支切割为核心算法框架，是解决实际供应链优化、网络流设计和生产调度问题的主力工具。

经济学与管理科学中的应用

分支定界法在经济学和管理科学中有着广泛的应用场景。在拍卖理论中，组合拍卖的胜者决定问题（Winner Determination Problem）可建模为整数规划，分支定界法是求解该问题的标准精确方法。在机制设计中，考虑激励相容约束的资源配置问题常涉及离散决策变量，需借助分支定界框架求解。在产业组织理论的实证研究中，进入/退出博弈的纳什均衡计算可归约为整数规划问题。此外，在管理科学实践中，车辆路径规划、仓库选址、机组排班和投资组合优化（含基数约束的均值-方差模型）等含离散决策的现实问题，均依赖基于分支定界的求解器获得可证明最优的决策方案。

尽管非凸优化和全局优化领域已发展出众多松弛和启发式方法，分支定界法仍然是唯一能在有限步内保证求得全局最优解并出具最优性证明的通用精确算法框架。其与计算复杂性理论的深层关联——即NP-难问题精确求解的指数时间下界——也使其成为理解优化问题难度分级的核心概念工具。