分支定界法是求解数学优化问题的一种通用框架:它系统地将问题划分为更小的子问题,并舍弃那些不可能包含比已找到的解更优的解的子问题。其核心特征是将分支与定界相结合:分支将可能的解组织成一棵搜索树,定界则为树中各部分所含解的质量确定界限。与穷举不同,它无须逐一考察所有可能性,就能成批排除其中的大量候选解。
这一框架在整数规划中尤为重要,因为这类问题要求部分或全部决策变量取整数值;它也广泛用于涉及选择、指派、排序或网络的组合问题。此外,它还是连续非凸优化中一些方法的基础。在界限有效、数值计算可靠的前提下,一次成功完成的分支定界计算不仅能给出最优解,还能提供不存在更优解的依据。
分支定界法并不是某一种固定的算法。它在实际中的表现取决于如何构造子问题、所给界限有多紧、如何发现有希望的解,以及优先探索搜索树的哪些部分。现代实现将松弛方法、推理、割平面、启发式方法和并行处理结合起来,因此,搜索树往往只是一个规模大得多的优化系统中的组成部分。
数学基础与术语
考虑如下最小化问题:
其中, 是可行集, 是目标函数。分支定界树中的节点 表示一个受限的可行集 。根节点表示原始问题。分支操作将一个节点替换为若干子节点,这些子节点的可行集合起来覆盖该节点尚余的所有可能性:
各子节点的可行集通常互不相交,但保证算法正确性的关键要求是覆盖性,而非互不相交性。
对于最小化问题,节点的界 必须满足
当前最优解是迄今找到的最佳可行解,其目标值为 。由于该解是可行的,它给出了最优值的一个上界:。如果 ,则节点 所代表的任何解都无法改进当前最优解,因此可以舍弃该节点。这一操作称为剪枝或节点判定终结。
对于最大化问题,不等号的方向相反。此时,节点需要一个可达目标值的上界,而当前最优解则提供一个下界。这一区别很重要,因为“界”既可能指从子问题中获得的信息,也可能指已知可行解的目标值。此外,还常使用原始界和对偶界这两个术语:对于最小化问题,当前最优解提供原始上界,而适当的节点松弛问题则提供对偶下界。
活跃节点是尚未处理完毕、也未被舍弃的子问题,其后代节点不一定已经生成。因此,这棵树表示的是一种隐式枚举:单个尚未处理的节点就可能代表数量庞大的候选解。借助界,可以一次性排除这整组候选解。
如果活跃节点覆盖了所有尚未解决的可能性,就可以构造如下全局下界:
其中, 是活跃节点集合,空集上的最小值约定为 。当当前最优解的目标值有限时,就有 。这两个值之间的区间衡量的是尚待证明的差距,而不一定是当前最优解与真正最优值之间的实际差距。
基本流程及其正确性
基本的分支定界算法从根节点、一个活跃节点集合开始,此时尚无当前最优可行解。对于最小化问题,当前最优可行解的目标值通常初始化为 。若在树搜索开始前已获得可行解,就可以立即用其目标值替换这一初始值。算法反复选取一个活跃节点,分析其对应的子问题,然后将该节点关闭或生成子节点。
典型的节点处理顺序如下:
- 执行计算开销较小的可行性检查,并收紧变量的取值域。
- 计算该节点所对应目标值的有效下界。
- 如果节点不可行,或其下界表明不可能改进 ,则舍弃该节点。
- 利用处理过程中发现的任何可行解更新当前最优可行解。
- 如果对子问题的求解已足以确定其中不再存在更优解,则关闭该节点。
- 否则进行分支,确保覆盖所有尚未排除的可能情况,并将子节点加入活跃节点集合。
终结节点通常有三种理由。不可行是指该节点对应的受限问题没有可行解。界支配是指该节点的下界不小于当前最优可行解的目标值。节点已求解是指该节点的最优值已经确定;例如,连续松弛问题的最优解可能已经满足所有要求的整数性条件。
算法的正确性源于一个不变式:每个可能改进当前最优可行解的可行解,要么由某个活跃节点或正在处理的节点表示,要么已经被考察过。分支通过保证覆盖性来维持这一不变式。不可行性剪枝不会排除任何可行解,界剪枝也不会排除任何能带来严格改进的解。一旦活跃节点集合为空,就不再有尚未探索且能够带来改进的解。因此,最优性的论证建立在数学证明之上,而不只是因为搜索未果就相信当前解最优。
寻找一个最优解与枚举所有最优解之间的区别,会改变剪枝规则。如果只需要一个最优解, 就足以进行剪枝。如果必须找出所有最优解,那么满足 的节点可能包含其他最优解,通常不能仅凭这一条件将其排除。
要保证算法在有限步内终止,还需要额外的假设。对于离散变量赋值组合有限的有界问题,只要节点操作能够终止,就可以采用最终能区分每一种赋值组合的分支规则来求解。连续问题则需要更谨慎地处理:区域细分可能无限持续,收敛性可能取决于区域不断缩小以及界的精度不断提高。分支定界法也不会自动判定无界性。尤其是,混合整数问题的松弛问题无界,本身并不能证明原问题存在目标值可以任意改善的可行解。
松弛与界的构造
获得界最常见的方法是求解一个松弛问题,即通过放宽或去掉某些限制,使问题更容易求解。如果 ,则
因此,对于最小化问题,松弛问题的最优值是一个有效的下界。只要能够证明这一不等式成立,松弛问题在计算上就不必与原问题相似。
对于混合整数线性优化,标准的松弛方法是去掉整数性约束,保留线性约束。对于如下形式的问题:
当允许其中指定的整数变量取实数值时,它就变成了一个线性规划问题。其最优值是原混合整数问题最优值的下界。如果松弛问题的某个最优解满足整数性约束,那么它也是该节点所对应的原子问题的最优解。
界也可以通过拉格朗日对偶、组合论证或专门的优化算法获得。对于含有难以处理的约束 的最小化问题,可以使用
对于原问题的每一个可行解,新增项都非正,因此 是一个下界。通过选择乘子使该下界最大化,可以显著增强界的紧致性。在路径规划问题中,忽略部分巡回路线要求而得到的低成本结构,也可以提供类似的界。
一个值得注意的区别是:松弛问题的可行解与经过验证的松弛界并不相同。对于最小化问题,松弛问题的可行解通常给出的是松弛最优值的上界,而不是对原问题进行安全剪枝所需的下界。相比之下,即使尚未将松弛问题求解至最优,对偶可行解也能提供有效的下界。因此,求解器的终止状态十分重要。
更紧的界并不总是意味着更高的计算效率。计算代价高昂的界虽然可能排除大量节点,但其耗时可能超过使用较廉价的界探索这些节点所需的时间。实际实现中往往会依次进行一系列检验,先做简单的算术检验或取值范围检查,只有在值得时才进一步求解计算成本较高的松弛问题。
无需重新求解松弛问题,也可以加强界。子节点可以继承父节点的有效下界。如果所有可行的目标函数值都是整数,就可以将任意有限实数下界 向上取整为 。更一般地,如果已知可达到的目标函数值之间的间隔,也可以据此进行类似的加强。这类推断必须以目标函数的实际结构为依据;仅仅存在整数变量,并不意味着目标函数值一定是整数。
分支规则与节点选择
分支决定了如何消除不确定性。在混合整数线性优化中,一种常见规则是选择一个松弛解取值 为非整数的整数约束变量,并创建两个子节点:
这两个分支涵盖了所有整数取值,同时排除了当前的非整数取值。若 ,两个子节点分别施加约束 和 。对于二元变量,便得到常见的两个分支: 和 。
有时会选择取值最接近半整数的变量,因为这样两个分支都能排除其所在相邻整数区间中的较大一部分。这种“最分数化”规则计算开销低,但没有考虑目标函数信息。强分支则试探性地求解或部分求解候选子节点的松弛问题,比较各候选分支预计带来的界的改进。它可以显著缩小搜索树,但测试大量候选分支的成本很高。
伪成本分支根据以往分支的观测结果,估计变量每移动一个单位所带来的界的改进,并分别维护向上和向下分支的估计值。可靠性分支将这两种方法结合起来:当估计值缺乏足够观测支持时,通过强分支获取信息;积累了足够的观测后,则使用伪成本。这些规则表明,分支决策不仅利用当前的松弛解,也利用搜索过程中收集的信息。
节点选择是另一个独立的决策。深度优先搜索沿着一条路径向下探索,通常能较快地找到完整的可行赋值,而且存储待处理的搜索前沿所需的空间相对较少。最佳界搜索在最小化问题中选择下界最小的活跃节点,将搜索资源投入到当前制约全局下界的那部分搜索树。广度优先搜索先处理较浅的层级,但其搜索前沿可能变得非常庞大。
仅仅快速找到当前最优可行解,或仅仅快速改进界,都不足以实现高效搜索。优质的当前最优可行解能促成更多剪枝,而更强的下界则能证明该解的质量。因此,实际求解器会结合多种策略,例如采用深度优先的下潜搜索来寻找可行解,再按最佳界顺序处理节点,以缩小尚未消除的最优性间隙。找到首个当前最优可行解后,或内存受限时,搜索顺序可能发生变化。
分支并不限于针对单个变量。调度问题可以根据某项任务是否先于另一项任务执行来分支;路径规划问题可以要求包含或禁止使用某条边;集合划分模型可以根据两个元素是否出现在同一组中来分支。关键要求是:各分支应覆盖所有相关解,推动搜索取得进展,并保留足够的问题结构,使子节点的界仍能以可承受的计算成本求得。
整数规划实例详解
考虑如下含两个变量的问题:
目标是在满足两个不等式的条件下,使两个非负整数变量之和最小。去掉整数约束,就得到一个连续线性规划。将两个约束相加可得
因此,松弛问题的每个可行点的目标值都至少为 。
点 使两个约束均取等号,并达到这一下界。因此,根节点松弛问题的最优值为 。由于两个坐标都不是整数,它并不能直接给出整数解。假设初步启发式算法已找到 ,得到当前最优可行解的目标值 。根节点的下界小于 4,因此还不能通过与当前最优可行解比较来剪枝。
对 进行分支,得到 和 两种情形。在第一个子节点中,由约束 可得
点 是可行点,目标值为 3。因此,它同时给出了该子节点松弛问题及其整数问题的最优解。当前最优可行解的目标值从 4 改进为 3,该子节点也就可以关闭。
对于第二个子节点,即 的情形,由另一个原始不等式可得
点 满足所有约束,且目标值为 3,因此第二个子节点的松弛最优值也为 3。由于当前最优可行解的目标值已经为 3,可以直接根据该子节点的界将其剪枝,无需再寻找另一个解。两个子节点均已关闭,由此证明原问题的最优值为 3。
这个例子还说明,更强的推断可以完全避免分支。由于 必须是整数,根节点下界 意味着
如果已经找到 或 中的任意一个,那么向上取整后的下界就等于当前最优可行解的目标值,从而可以在根节点证明最优性。
不同的输出要求会带来不同的处理方式。如果只需找到一个最优解,就不必在第二个子节点中求出具体的解。如果要枚举所有最优解,仅凭该子节点的下界等于 3,还不足以将其舍弃。点 和 都能达到最小值,因此,旨在寻找所有最优解的算法必须保留找到这两个解的可能性。
分支切割法、分支定价法与约束推理
现代混合整数求解器通常利用割平面法来强化分支定界法。割是一个不等式,所有相关的整数可行解都满足它,但当前松弛问题中的某些点不满足它。加入这样的不等式,可以排除松弛问题的分数解,同时不排除有效的整数解。这种组合框架称为分支切割法。
对于一个二元选择问题,假设物品集合 的总重量超过可用容量。这些物品就不可能全部被选中,因此
是一个有效不等式。这种覆盖不等式可以强化背包问题的松弛。其他类别的割则利用整数性、逻辑蕴含关系或网络结构。衡量割的效益时,不仅要看它能立即将界改进多少,还要考虑它对后续节点松弛问题的影响。
割可以是全局有效的,也可以是局部有效的。全局割在原问题的整个可行集上都成立,可以在整棵搜索树中使用。局部割则依赖于某条搜索路径上施加的限制,仅在相应节点的子树内有效。错误地将局部不等式当作全局不等式使用,可能会排除有效解。因此,割的管理不仅包括在松弛问题规模增大时决定保留哪些不等式,还包括管理这些不等式的有效范围。
另一种扩展方法针对的是变量过多、无法显式列出所有变量的模型。列生成通过求解受限主问题,并利用定价问题找出可能改善主问题解的未纳入变量。将这一过程与分支相结合,就得到分支定价法。典型应用包括车辆路径规划和机组排班;在这些应用中,一个变量可以代表一条完整的可行路线或一项完整的执勤任务。
分支定价法中的定界需要谨慎处理。对于最小化主问题,仅使用受限列集得到的最优值,并不一定是完整线性松弛问题最优值的下界。要得到有效的节点界,必须完成定价过程,或通过其他严谨论证将未纳入的列考虑在内。分支施加的限制也必须转化为定价问题中的相应限制,因此,适用的分支规则可能不同于普通的变量分支规则。
推理可以作为上述两种方法的补充。约束规划通过传播逻辑和数值上的推论来缩小变量的取值域。例如,当某项资源已用满时,就可以立即排除需要额外消耗该资源的选择。分支定界法可以在求解用于定界的优化松弛问题之前进行这类传播。反过来,约束规划中的优化求解也可以记录当前最优目标值,并排除不可能取得更优目标值的部分赋值。这些方法的区别主要在于信息的表示和传播方式,而非彼此之间存在绝对界限。
连续与混合整数全局优化
当搜索空间连续,且目标函数或约束非凸时,分支定界法同样适用。局部优化方法可能找到一个驻点,却无法证明它是全局最优点。在全局优化中,分支定界法将变量的定义域划分为若干区域,在各区域上构造有效的下界,并将其与通过局部搜索或其他方法获得的可行目标值进行比较。
一种常见的表示方式是将每个节点对应于一个箱形区域:
分支操作将其中一个区间分割,分割点通常取区间中点,或选定的松弛解取值。难点在于构造一个在整个箱形区域上都有效的低估函数。当非凸问题被适当的凸松弛所替代时,便可通过凸优化求得界。
对于双线性项 ,其中 、,McCormick 不等式为
这些不等式刻画了单个双线性项在其矩形定义域上的函数图像的凸包。当模型包含多个相互关联的乘积项时,分别对各项施加这些不等式,通常并不能刻画整个可行集的凸包。
细分区域能够收紧这些松弛,因为变量区间越窄,非线性表达式与其凸包络或其他低估函数之间的差距就越小。界也可以通过区间算术获得;区间算术给出一个包含表达式在某一区域上所有可能取值的区间。直接进行区间求值所得到的界可能较弱,因为它在处理同一变量的多次出现时,未能充分利用这些出现之间的依赖关系;更精细的松弛方法和定义域缩减可以缩小所得到的包围区间。
连续空间上的搜索未必能在有限次细分后终止并得到精确最优解。不过,在适当的紧致性和一致性条件下,通过不断缩小区域并使界收敛,可以确定一个满足给定绝对容差的解。当 时,当前最优可行解的目标值 与有效的全局下界 便能证明该解具有 -最优性。保证这种收敛性的条件取决于具体的定界与细分方案,而不是仅凭“分支定界法”这一名称就能成立。
混合整数非线性规划将离散分支与这种空间细分相结合。求解器可以对整数变量进行分支,以满足整数性要求,也可以对连续变量进行分支,以收紧非线性松弛。如果在适当的模型表述下,所有非线性部分均为凸的,那么凸子问题就能提供全局界;非凸模型则需要额外的全局定界机制。
数值可靠性、终止间隙与实现
数学上的剪枝规则以有效的界和可行的当前最优解为前提。计算机实现通常采用浮点运算,因此约束残差、目标函数值和整数性检查都是近似的。例如, 这样的数值可能在容差范围内被视为整数,但直接对向量各分量取整可能违反相互耦合的约束。因此,可行性检查和容差也是在实际应用中解读求解器结果时必须考虑的因素。
当界接近当前最优解的目标值时,数值问题尤为重要。如果最小化问题的下界被意外高估,就可能错误地剪除包含更优解的区域。尺度设置不当以及约束之间近似线性相关,都可能加剧这种风险。在逻辑关系的数学建模中,采用过大的人工常数既可能削弱松弛,也可能加重数值问题。这些问题将分支定界法与数值稳定性及底层线性代数问题的条件性联系起来。
求解器通常会报告绝对最优性间隙 和相对间隙。一种可能的定义是
但具体定义各不相同,尤其是在数值接近零或上下界异号时。只有同时说明所用的分母和终止规则,相对间隙才有明确意义。在界有效的前提下,以正间隙终止可以保证目标函数值在规定容差范围内,但并不能证明它与最优值完全相等。
高效的节点处理在很大程度上依赖于信息复用。子节点的松弛问题与父节点相比,往往只有一两个变量的界发生变化,因此复用线性规划的基或其他热启动数据,可以显著减少重新优化的工作量。节点可以只存储相对于祖先节点的改动,而不必保存模型的完整副本。预求解可以在搜索树大规模展开之前,去除冗余约束、固定变量,或检测出不可行性。
并行计算允许同时处理多个节点。各工作进程共享改进后的当前最优解、选定的割以及其他信息。负载均衡并不容易,因为表面上相似的子树可能需要截然不同的工作量。搜索顺序也会影响剪枝:某个工作进程若较早找到质量较高的当前最优解,就可能省去其他位置的搜索工作,从而获得高于将固定工作量简单均分所能带来的加速比。其他调度方式则可能推迟这一发现,导致额外的工作。
若要进行更严格的认证,可以采用有理数重构、精确算术或经过验证的数值包围区间。对于适用的线性模型,证书可以包含用于证明松弛问题界的精确对偶信息,以及每个已关闭分支的明确证明依据。这类认证不同于普通浮点求解器的日志。日志记录的是计算进程,而可供独立检查的证书必须能够证明各项排除操作在数学上有效,因为最优性声明正是建立在这些排除操作之上的。
计算复杂度与实际应用
分支定界法是一种精确求解框架,并不是解决困难优化问题的通用多项式时间方法。对于 个二元决策,穷尽式分支可能产生 个完整赋值,以及一棵规模同样呈指数级增长的二叉树。好的界限可以在特定实例上大幅缩小搜索规模,但较弱的松弛可能迫使算法遍历搜索树的大部分节点。许多重要应用都具有 NP难性,因此,采用分支定界法并不意味着对所有实例都能高效求解。
性能取决于模型表述与搜索过程之间的相互作用。两个模型可以描述相同的可行决策,却产生差异很大的连续松弛。如果一个模型的松弛能够紧密逼近可行整数点的凸包,可能只需进行少量分支。另一个模型即使变量更少,若界限较弱,也可能难以求解得多。对称性是另一重障碍:可互换的机器、车辆或设施,可能使本质上相同的决策具有许多不同的表示。
旅行商问题体现了松弛结构的重要性。仅保留度约束的松弛可能选出若干互不连通的环,而不是一条完整的巡回路线。连通性不等式可以排除这类子回路,在分支之前或分支过程中收紧界限。在车辆路径问题中,基于路径的模型可能具有很强的松弛,但规模极其庞大,因此往往需要采用分支定价法或分支割定价法,而不是简单地以边变量构建搜索树。
在调度和资源分配应用中,分支用于确定分配方案、不同的开始时间选项或先后关系。计算界限时,可以忽略某些资源冲突、放松整数性要求,或将问题分解为更简单的部分。设施选址模型需要决定开设哪些设施,以及如何满足需求;生产模型则将连续的生产数量与离散的生产准备决策相结合。在这些应用中,实际采用的方法都取决于模型的结构,而不是某种通用的分支套路。
分支定界法与动态规划的主要区别,在于减少计算量的方式。动态规划通过合并重复状态,或利用子问题之间的递推关系来减少计算。分支定界法则主要依据目标函数的界限排除搜索区域。不过,这两种方法也可以结合:动态规划可以用于求解节点的松弛问题、计算组合界限,或识别被支配的部分决策。
分支定界法也不同于模拟退火这类启发式方法,后者可能找到非常好的可行解,却无法证明其质量。启发式方法在分支定界法内部很有价值,因为当前最佳解的每一次改进,都可能增强整棵搜索树上的剪枝效果。限时运行可能返回一个有用的解,同时给出一个非零、且有严格保证的最优性间隙;其主要成果究竟是找到解,还是证明解的质量,取决于具体应用以及当时界限的情况。
历史发展
分支定界法起源于二十世纪中叶的运筹学。当时,电子计算机使系统性的离散搜索日益可行,但穷举的计算成本仍然高得难以承受。其起源涉及几项相互关联的发展:离散规划方法、组合路径规划算法,以及更一般的有界树搜索表述。这一框架是在这些方法的相互影响中逐步发展起来的,而非源于某个一成不变的算法。
艾尔莎·H. 兰德(Ailsa H. Land)和艾莉森·G. 多伊格(Alison G. Doig)于1960年发表的论文《求解离散规划问题的一种自动方法》是一项奠基性贡献。她们的方法利用线性规划松弛和系统性细分来求解离散优化问题,为后来形成的混合整数分支定界法奠定了影响深远的基础:通过连续优化提供界,再通过逐步添加约束来落实离散性要求。
约翰·D. C. 利特尔(John D. C. Little)、卡塔·G. 穆尔蒂(Katta G. Murty)、杜拉·W. 斯威尼(Dura W. Sweeney)和卡罗琳·卡雷尔(Caroline Karel)于1963年发表的论文《旅行商问题的一种算法》是另一项里程碑式成果,也推动了“分支定界”这一术语的确立。他们的方法将有关巡回路线中各条边的决策组织成一棵搜索树,并利用约化代价矩阵计算界。这项研究展示了如何借助针对特定问题设计的定界过程,将概念上的穷举搜索转变为选择性强得多的搜索。
埃贡·巴拉斯(Egon Balas)于1965年提出的加性算法,通过隐式枚举和逻辑检验,为零一整数规划提供了一种颇具影响力的求解方法。虽然其计算机制不同于反复求解线性规划,但它同样致力于在不逐一列举的情况下排除整批赋值方案。这些进展表明,精确离散优化可以利用多种形式的定界与推理。
割平面法与树搜索并行发展。拉尔夫·戈莫里(Ralph Gomory)在20世纪50年代末的研究提供了一种通用方法,能够推导出排除松弛问题分数解、同时保留整数解的不等式。此后,将割与分支相结合,形成了分支割法。分解方法和列生成方面的研究也为分支定价法奠定了基础,尤其适用于那些以复杂组合对象作为自然变量的模型。
后续进展有赖于整个计算系统各个环节的改进,包括更快的线性规划方法、预求解、更好的分支决策、原始启发式算法、更强的割生成方法,以及更高效的数据结构。在非线性优化中,凸包络和空间细分将同样的定界原理扩展到了离散域之外。当代研究仍在探索通过学习获得的分支策略和节点选择策略,其中包括运用机器学习的方法。这类策略可以影响搜索效率,但最优性结论的有效性仍然取决于可靠的界、保持搜索空间覆盖的分支,以及具有充分依据的剪枝。