分支定界法 (Branch and Bound)
- 提出者
- Ailsa Land & Alison Doig
- 年份
- 1960
- 类型
- Exact combinatorial optimization algorithm
- 类别
- Mathematical programming
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
分支定界法是一种用于组合优化和整数规划问题的系统性精确算法,由 Ailsa Land 和 Alison Doig 于 1960 年提出。它将搜索空间组织成一个子问题树,利用松弛法导出的上界来剪除无法改进已知最优解的分支,并保证找到全局最优整数解。它是运筹学、物流、调度和工程设计中现代混合整数规划求解器的基石。
方法背后的直觉
想象一下在一个巨大的房间迷宫中寻找价值最高的物品。你不需要检查每个房间,而是在进入每个走廊之前估计从该走廊能达到的最大可能价值。如果这个上限低于你已持有的最佳物品的价值,你就会跳过整个走廊而不进入。分支定界法的工作原理类似:它将问题分解成更小的部分,计算每个部分的乐观上界,并立即丢弃那些可以证明无法超越当前最佳解决方案的任何部分。
历史学
Land 和 Doig 于 1960 年在《Econometrica》上发表了基础性的分支定界法论文,将其构建为一种自动化的离散规划方法。Little 等人(1963 年)将其应用于旅行商问题,巩固了其在组合优化中的地位。Dakin(1965 年)引入了 LP 松弛分支,这是当今最常用的形式。随后的几十年里,割平面(分支割算法)和列生成(分支定价算法)被整合进来,使分支定界法成为所有主要商业整数规划求解器的引擎。
何时使用
当您必须找到混合整数或纯整数线性规划问题的可证明最优解,并且不能接受近似答案时,请使用分支定界法。它假定问题可以通过提供有用界的线性(或凸)松弛来构建。对于搜索树爆炸的非常大的实例、没有紧密松弛的非线性整数规划或计算时间严格受限的实时设置,它不太适用。在这些情况下,启发式或元启发式方法可能更受青睐。
局限与注意事项
- 最坏情况复杂度为指数级;在结构不良的实例上,搜索树可能变得大到不切实际。
- 性能高度依赖于分支变量和节点选择策略的选择。
- 需要一个可处理的松弛,该松弛能提供有意义的上界;弱界会导致最小的剪枝。
- 当必须同时存储许多开放节点时,内存需求可能很大。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 保证整数和组合规划问题的全局最优性。
- 通过基于界的剪枝极大地减少了搜索——通常只探索了完整枚举树的一小部分。
- 灵活性:可以整合割平面(分支割算法,branch-and-cut)或启发式界(分支定价算法,branch-and-price)以进一步提高效率。
- 广泛应用于成熟的商业求解器(CPLEX、Gurobi)和开源工具(GLPK、CBC)中。
应用
- 运筹学中的航空公司机组调度和机队分配。
- 供应链网络设计和设施选址问题。
- 计算机工程中的 VLSI 电路布局和寄存器分配。
- 计算生物学中的蛋白质结构预测和基因组组装。
- 具有基数约束的金融投资组合优化。
使用方式
使用方式
算法开始时,会求解一个松弛后的问题版本——通常是线性规划 (LP) 松弛——忽略整数约束。由于每个可行的整数解在松弛问题中也是可行的,因此该松弛给出了真实最优值的上界。如果松弛解恰好是整数值,则问题立即解决。
公式
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}当松弛解包含一个分数变量时,算法通过添加互补约束来划分可行域,迫使该变量取其下界或上界。每个划分在搜索树中创建一个新的子节点,有效地将一个子问题分解为两个具有更紧域的更小子问题。
公式
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil每个活动节点都有自己的 LP 松弛界。一个界不超过已找到的最佳整数解(称为当前最优解)的节点,不可能包含更好的解,因此被剪枝。紧密的界至关重要:界越紧,需要探索的节点就越少。
公式
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}节点在三种情况下被剪断(永久关闭):其松弛不可行,其界不优于当前最优解,或者其松弛解已经是整数可行的。在最后一种情况下,如果新解改进了当前最优解,则更新当前最优解。当所有节点都被剪断时,算法终止,此时当前最优解就是全局最优解。
公式
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)常见陷阱
- 选择不当的分支变量(例如,总是对第一个分数变量进行分支)通常会导致深度不平衡的搜索树和收敛缓慢。
- 忽略有效不等式(割平面)意味着错失了显著收紧松弛界的机会。
- 过早终止并出现未报告的次优间隙可能会误导实践者将近优解视为精确解。
- 将分支定界法应用于非线性或非凸松弛,而没有专门的凸化处理,可能会产生无效的界和不正确的结果。
常见问题
分支定界法与穷举枚举有何不同?
穷举枚举显式地评估每个可行的整数解,这对于大型问题在计算上是不可行的。分支定界法通过在搜索树的每个节点计算基于松弛的上界,并在界无法超过已找到的最佳解时剪枝整个子树来避免这种情况。实际上,只检查了树的一小部分。
LP 松弛在分支定界法中起什么作用?
LP 松弛放宽了整数约束,使得问题可以通过单纯形法或内点法在多项式时间内求解。其最优值作为相应整数子问题的上界。当这个界很紧——接近真实的整数最优值时——需要探索的分支就越少。通过添加有效不等式获得的更紧的松弛会极大地加速整个算法。
何时应使用分支定界法而非遗传算法等元启发式方法?
当您需要最优性证明并且可以承受计算时间时,请选择分支定界法。它非常适合具有良好结构化 LP 松弛的中等规模问题。当问题极其庞大、缺乏有用的松弛,或者必须在严格的时间预算内解决且可接受近优解时,元启发式方法是首选。许多实践者将两者结合使用:将分支定界法与早期终止的间隙容差一起使用。
相关方法
参考文献
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
打开 DOI 文献已复制。