1 基本概念
分支定界法是一类用于求解组合优化与整数规划问题的精确算法框架。它的基本思路是把原问题拆分为一系列规模更小的子问题，并通过对这些子问题计算上下界，判断哪些分支仍有可能产生更优解，哪些分支可以直接舍弃。由于该方法能够在理论上保证全局最优性，因此在需要严格最优解的场景中应用广泛。
1.1 方法定义
分支定界法通常指在搜索过程中，对问题空间进行递归划分，并为每个子问题建立界限估计的求解方法。若某个子问题的最优可能值已不优于当前已知解，则可停止继续探索该子问题。该方法兼具搜索与筛选两种机制，是精确优化算法中最具代表性的框架之一。
1.2 核心思想
其核心思想可概括为“分而治之，加界剪枝”。分支负责把复杂问题拆解为若干互斥子问题，定界负责快速判断子问题的潜在优劣，剪枝则用于减少不必要的计算。通过这种方式，算法不必穷尽所有可行方案，而是尽量只保留“仍可能成为最优”的部分。
1.3 适用问题类型
分支定界法适用于具有离散决策特征、可行解空间有限且目标函数可评价的问题。尤其当问题规模较大、直接枚举代价过高时，该方法往往更具实际价值。
1.3.1 组合优化问题
组合优化问题通常要求在有限的离散方案中选出最优解，例如路径选择、集合选择与任务分配等。此类问题的候选解数量常随规模迅速增长，分支定界法可以通过逐步排除无效方案来控制搜索范围。
1.3.2 整数规划问题
整数规划要求部分或全部决策变量取整数值。由于连续松弛后的问题往往更易求解，分支定界法常将整数约束分解到子问题中处理，从而逐步逼近整数最优解。
1.3.3 NP难问题
许多 NP 难问题在最坏情况下难以用多项式时间求解，但分支定界法仍可作为通用精确工具使用。它不承诺快速完成，却能在可接受规模内提供严格最优结果，因此常被用作基准求解框架。
1.4 与其他优化方法的关系
分支定界法与回溯法在搜索结构上有相似之处，但前者更强调通过界值进行剪枝。它也常与动态规划、割平面法、启发式搜索等方法结合，以增强界限质量或加速找到可行解。在许多求解器中，分支定界法是底层核心机制之一。
2 算法原理
分支定界法的运行依赖三个关键环节：分支、定界和剪枝。算法从根结点出发，反复生成子问题，并对其可达最优值进行估计。若估计结果表明该分支不具备竞争力，则直接舍弃，从而避免无效搜索。
2.1 分支机制
分支机制用于把原问题拆解为更小的子问题，使每个子问题都继承原问题的一部分约束，同时增加新的限制条件。这样做的目的在于逐步收缩可行域，直到某个结点对应的问题足够简单或已可直接判定。
2.1.1 决策变量选择
分支时首先需要选定一个关键变量，通常是当前松弛解中最“违反整数性”或最能影响目标值的变量。变量选择是否合理，会显著影响搜索树的规模与算法效率。
2.1.2 子问题划分
选定变量后，通常根据其取值范围将问题划分为若干互斥子问题。例如，对整数变量 x，可分别加入 x≤k 与 x≥k+1 之类的约束。这样得到的子问题覆盖原问题可行域，但彼此不会重复。
2.2 定界机制
定界机制用于估计子问题的潜在最优值。若是最小化问题，通常关注下界；若是最大化问题，则更常使用上界。界限越紧，剪枝越有效。
2.2.1 上界与下界
上界表示当前子问题最好的可能结果，或已知可行解的目标值上限；下界则表示该子问题理论上不可能优于的最低水平。通过比较当前最优可行解与子问题界值，算法可以判断是否继续搜索。
2.2.2 松弛问题求解
常见做法是先去掉部分难处理约束，如整数约束，得到一个更易求解的松弛问题。松弛问题的最优值通常可作为原问题界限的估计。若松弛模型足够接近原问题，则定界效果会更好。
2.3 剪枝规则
剪枝是分支定界法效率提升的关键。通过舍弃不可能产生更优解的结点，算法能够显著缩小搜索空间。
2.3.1 界限剪枝
若某子问题的界值已不优于当前最优解，则该子问题无继续探索的必要。这类剪枝最常见，也最依赖界限质量。
2.3.2 可行性剪枝
若子问题本身已经无可行解，或者在现有约束下不可能构造出合法解，则可直接删去。此类判断可来自约束矛盾、变量域空缺或松弛模型不可行。
2.3.3 最优性剪枝
当某结点已得到一个可行解，且其目标值已达到可证明的最优水平时，相关分支可以停止扩展。此时算法会将该解作为全局最优解记录下来。
2.4 搜索树结构
分支定界法通常以树形结构组织整个求解过程。每个结点对应一个子问题，树中的路径则表示一系列逐步加入的约束条件。
2.4.1 结点表示
结点一般记录当前子问题的约束状态、界值、松弛解以及是否已被处理等信息。对于复杂实例，还可能附带分支变量、深度层数和父结点指针等数据。
2.4.2 叶结点判定
当某个结点已经无法继续分裂，或其子问题足以直接求解时，就会被视为叶结点。叶结点可能对应一个完整可行解，也可能因不可行或被剪枝而终止。
3 算法流程
分支定界法的流程通常围绕“初始化—扩展—判断—终止”展开。实际实现中，流程会因具体问题和定界方式而略有差异，但整体框架相对稳定。
3.1 初始化
初始化阶段负责建立求解的起点，并尽量获得一个较好的初始可行解，以便为后续剪枝提供参考。
3.1.1 根结点构建
根结点通常代表原始问题本身，不附加额外分支约束。算法从根结点开始计算其松弛界，并据此决定后续搜索方向。
3.1.2 初始界获取
初始界可以来自启发式方法、简单贪心解或已有近似算法结果。若初始解质量较高，后续大量弱势分支会更早被剔除。
3.2 结点扩展
结点扩展是算法的主体过程。每次从活结点集合中取出一个结点，计算其可扩展性，然后生成更细粒度的子问题。
3.2.1 分支策略
分支策略决定在哪里拆分问题，以及如何构造子结点。不同策略会影响搜索树形状，进而影响总计算量。
3.2.2 结点排序
对于多个待处理结点，算法通常按照某种优先级进行选择，例如先处理界值最优者，或先处理深度较浅者。排序机制直接关系到是否能尽快发现高质量可行解。
3.3 终止条件
算法会在满足一定条件时结束，例如已确认全局最优，或计算资源达到上限。终止条件的设计既要保证正确性，也要兼顾实际可执行性。
3.3.1 全局最优确认
当所有活结点都被剪枝或已完全处理，且当前最优可行解与剩余结点界值之间不存在改进空间时，即可确认全局最优性。
3.3.2 计算资源限制
在工程应用中，算法也可能因时间、内存或迭代次数限制而提前停止。此时通常返回当前最佳可行解及其界值信息，而不一定给出最优性证明。
3.4 伪代码表示
分支定界法的伪代码通常包括：建立根结点、计算界值、将结点加入活结点集合、循环选择结点、判断可行与否、必要时分支、更新全局最优解并执行剪枝，直至集合为空或满足终止条件。其结构清晰，便于与其他优化组件组合实现。
4 常用定界方法
定界质量直接影响分支定界法的整体性能。实际应用中，常使用多种估计手段，以在计算代价与界限紧度之间取得平衡。
4.1 线性松弛
线性松弛是最常见的定界方式之一，主要通过去掉整数约束将问题转化为线性规划。由于线性规划可高效求解，所得最优值可作为较实用的界限来源。
4.2 凸松弛与整数松弛
对于具有非线性或非凸特征的问题，常通过构造凸松弛模型获得可计算的界。整数松弛则保留部分离散结构，以便在精度与复杂度之间折中。
4.3 启发式估计界
启发式方法可快速给出一个近似可行解，从而提供上界或下界参考。虽然这类界通常不如严格松弛紧，但计算速度快，适合用于早期剪枝。
4.4 拉格朗日松弛
拉格朗日松弛通过将某些难处理约束并入目标函数，并配合乘子调整来求界。它在许多结构化组合优化中效果良好，尤其适合约束分解明显的场景。
4.5 割平面辅助定界
割平面法可在松弛模型中加入额外有效不等式，使松弛解更接近整数可行域。作为定界辅助手段时，它常能显著提高界限紧度，从而减少搜索结点数。
5 典型分支策略
分支策略决定算法如何切分问题。合适的策略不仅能提升剪枝效率，还能帮助更快定位高质量解。
5.1 按变量分支
按变量分支是最直接的方式，即针对某个决策变量构造若干子问题。对于整数规划和背包类问题，这种方式最为常见，结构也较容易实现。
5.2 按约束分支
某些问题更适合按约束条件而非单个变量进行分裂，例如围绕某一可行性条件建立子问题。该策略常用于结构较复杂、变量关联较强的模型。
5.3 按值域分支
当变量取值范围较大时，可通过将值域划分成若干区间来进行分支。此法适合连续变量离散化或多阶段决策问题。
5.4 按区域分支
在几何优化或空间搜索问题中，常把可行区域划分为更小的子区域。每个子区域对应一个局部搜索范围，便于逐层缩小候选空间。
5.5 最优分支变量选择准则
分支变量的选择通常综合考虑整数违背程度、对目标函数的影响、对界限的改善潜力等因素。常见准则包括最接近分数值、最大代价贡献、最强分裂效果等思路。
6 结点搜索策略
结点搜索策略决定活结点的处理顺序。不同顺序会影响找到可行解的速度、内存消耗以及最终搜索树规模。
6.1 深度优先搜索
深度优先搜索倾向于沿当前分支不断向下探索，直到无法继续为止。它的优点是内存占用较小，且常能较快找到一个完整可行解。
6.2 广度优先搜索
广度优先搜索优先扩展较浅层结点，有利于系统性地覆盖搜索空间。其缺点是活结点数量增长较快，内存压力往往较大。
6.3 最佳优先搜索
最佳优先搜索根据界值或其他评分规则选择最有希望的结点扩展。该策略常能更快逼近最优解，但维护优先队列的代价较高。
6.4 混合搜索策略
混合策略会结合深度、广度与最佳优先的优点，例如先深搜获取可行解，再按界值优先清理高潜力结点。此类方法在实际求解器中非常常见。
6.5 活结点管理
活结点管理涉及结点的存储、取出和删除。高效的管理机制可以减少重复计算，并支持在大规模实例中维持稳定性能。
7 性能影响因素
分支定界法的实际效率受多种因素制约。不同问题、不同建模方式乃至不同实现细节，都可能导致性能差异明显。
7.1 问题规模
规模越大，潜在搜索空间通常越广，结点数也可能指数级增长。若问题尺寸上升过快，即便使用剪枝，计算时间仍可能显著增加。
7.2 松弛质量
松弛模型越紧，界限越接近真实最优值，剪枝越容易发生。相反，若松弛过于宽松，算法就会探索大量无效分支。
7.3 分支顺序
分支顺序决定哪些变量或约束先被细化。好的顺序往往能更快发现高质量解，并让不良分支提前被淘汰。
7.4 剪枝效率
剪枝效率取决于界限判断是否敏锐、可行性检测是否及时。若剪枝机制反应迟缓，算法就会在低价值结点上消耗过多资源。
7.5 初始可行解质量
较强的初始可行解可以显著提升上界或下界水平，使得更多分支在早期被排除。工程上，先用启发式算法找一个“还不错”的解，常是提升性能的有效手段。
8 复杂度分析
分支定界法的复杂度分析通常以最坏情况为重点，因为其性能高度依赖实例结构。在某些良好结构的实例中，它可能表现高效；但在一般情形下，仍可能遭遇指数级增长。
8.1 最坏情况复杂度
最坏情况下，算法可能几乎遍历所有组合分支，时间复杂度呈指数级增长。对于 NP 难问题，这种情况并不罕见，因此分支定界法并不能从理论上消除困难性。
8.2 平均表现与实例差异
平均性能往往比最坏情况乐观得多，尤其当问题具有强结构、良好松弛或易于剪枝时。不同实例之间的差异可能非常大，某些数据集很快收敛，而另一些则难以处理。
8.3 时间与空间开销
时间开销主要来自结点扩展、松弛求解与优先级维护。空间开销则与活结点数量密切相关，尤其在广度优先或高分支度场景下更为明显。
8.4 可扩展性讨论
分支定界法的可扩展性受制于搜索树爆炸问题。为提升扩展能力，实际系统通常引入并行计算、强界限技术和问题特定预处理，以提高单位资源的求解能力。
9 改进与扩展
为了应对大规模或结构复杂的问题，分支定界法经常与其他优化技术结合，形成更强的混合框架。
9.1 分支定界与割平面结合
该组合先通过割平面增强松弛模型，再利用分支定界进行系统搜索。二者结合后，界限通常更紧，搜索树也更小。
9.2 分支定价
分支定价常用于具有大量变量的优化模型，通过“定价”过程动态生成有价值的变量，再在分支框架下推进求解。它在列生成问题中尤为常见。
9.3 分支剪切法
分支剪切法将剪切平面与分支搜索深度结合，在不断添加有效不等式的同时维持整数搜索。它是现代整数规划求解器的重要核心思想之一。
9.4 并行分支定界
并行化方法通过多个处理单元同时探索不同结点，以缩短总求解时间。关键难点在于负载均衡、共享全局界值以及避免重复搜索。
9.5 与元启发式方法的混合
元启发式方法可用于快速寻找高质量初始解或指导分支顺序，而分支定界法则负责最终的最优性证明。二者结合常能在速度与严谨性之间取得较好平衡。
10 应用领域
分支定界法适用于多种离散决策问题，尤其是那些既需要精确解又存在明显组合爆炸的场景。
10.1 调度问题
在作业排序、机器排程和项目安排中，分支定界法可用于寻找最优顺序或最小完工时间方案。由于约束复杂，常需要借助强定界和专门分支规则。
10.2 背包问题
0-1 背包是分支定界法的经典应用之一。通过对物品选择进行分支，并利用价值密度构造上界，算法常能有效排除大量无效组合。
10.3 旅行商问题
旅行商问题要求寻找最短闭合巡回路径。分支定界法通常配合路径松弛、下界估计和割平面使用，以缩小候选边集合。
10.4 图论优化问题
在图着色、最大团、最小割变体等问题中，分支定界法可通过逐步限制顶点或边的状态来推进搜索。其效果往往取决于图结构与界限构造方式。
10.5 设施选址与资源分配
设施选址和资源分配问题常涉及离散决策与成本最小化。分支定界法可在多方案之间筛选最优布局，适合中小规模高精度求解。
11 实现细节
实际实现分支定界法时，除了算法框架外，数据组织、界值更新和数值处理也很重要。细节设计直接关系到稳定性和运行效率。
11.1 数据结构设计
常见数据结构包括结点对象、活结点容器、状态表和结果记录表。良好的结构设计便于快速复制子问题、回溯父结点以及维护全局信息。
11.2 界计算模块
界计算模块应尽量独立，以便替换不同的松弛求解器或启发式估计器。模块化设计还可降低实现复杂度，增强可扩展性。
11.3 结点优先队列
当使用最佳优先搜索时，优先队列是核心组件。它负责按界值或评分函数组织待处理结点，并支持高频插入与弹出操作。
11.4 记忆化与缓存
对于重复出现的子结构或松弛结果，缓存可减少重复求解成本。尤其在递归式实现中，记忆化有助于提高局部效率。
11.5 数值稳定性处理
在浮点计算环境下，界值比较可能受到舍入误差影响，因此需要设置容差。对松弛求解器的结果进行稳定性校验，也有助于避免误剪枝或漏剪枝。
12 经典案例
分支定界法在多个标准问题上都有清晰的示例价值，这些案例常用于教学、算法验证和求解器测试。
12.1 0-1背包求解
在 0-1 背包中，每件物品只能取或不取。分支定界法通常按物品逐个分支，并以分数背包解作为上界，从而加速剪枝。
12.2 整数线性规划求解
对于整数线性规划，算法会先求线性松弛，再对非整数变量继续分支。通过不断缩小变量区间，最终得到满足整数约束的最优解。
12.3 最短路径变体求解
某些最短路径变体加入了访问次数、资源消耗或额外结构约束后，会变得难以直接处理。分支定界法可在路径组合空间中逐步搜索可行方案。
12.4 排产问题求解
排产问题往往需要协调机器容量、工序顺序与截止时间。分支定界法可对任务排列进行分支，并利用时间窗界限减少无效排程。
13 相关概念
分支定界法与多种经典优化思想密切相关，理解这些概念有助于把握它的定位与优势。
13.1 枚举法
枚举法是对所有候选解逐一检查的直接方法。相比之下，分支定界法通过界限信息减少了大量不必要的枚举。
13.2 动态规划
动态规划通过状态转移求解具有重叠子问题结构的优化任务。某些问题中，动态规划可作为分支定界的界值计算工具或辅助子程序。
13.3 回溯法
回溯法同样采用树形搜索并在不满足条件时回退，但通常更强调约束满足而非界值比较。分支定界法可看作带有定量评估机制的更一般搜索框架。
13.4 割平面法
割平面法通过不断加入有效不等式来缩小松弛可行域。它常与分支定界法结合，形成更强的整数规划求解流程。
13.5 启发式搜索
启发式搜索使用经验规则快速引导搜索方向，通常不保证最优性。分支定界法则在启发式基础上加入严格界限与证明机制，因此更适合精确求解。