做了这么多年运筹优化见过不少把MIP模型扔给求解器就撒手不管的情况。几十个变量的小问题默认参数确实能跑出结果可一旦变量数涨到几十万、上百万约束铺开几千甚至上万行黑盒求解器往往会暴露真实水平——要么根节点松弛解不出来要么上下界缩得很慢要么内存先爆掉。这篇文章想聊的就是大规模MIP的精确算法和实现层面的那些事分支定界为什么能保证最优分支切割、预处理、割平面、启发式各自承担什么职责以及工程实现里有哪些容易被忽略的细节。适合已经用过求解器、但想往更深一层走的同学也适合被大规模整数规划折磨过的从业者。1. 大规模MIP的难点在哪黑盒求解器的真实困境1.1 规模带来的三个层次麻烦MIP的数学形式不难理解在一组线性约束下让一部分变量取整数值极小化目标函数。可一旦投入实际应用规模带来的麻烦立刻变得具体。第一层麻烦是组合爆炸。假设有一个纯0/1问题只有50个0/1变量最坏情况下要遍历2的50次方种组合这个数字远超任何机器的枚举能力。即便求解器聪明的分支不会遍历全部组合整数变量个数只要超过几百个搜索空间就足够让朴素算法彻底崩溃。第二层麻烦是松弛太弱。求解器内部依赖LP松弛来获得下界如果模型里存在大量Big-M约束、弱线性松弛分数解会离整数解很远那么下界很低剪枝几乎不起作用分支树就会疯狂扩张。这个问题在小规模上不明显因为哪怕剪枝不高效反正问题小兜底也能跑完但大规模下每个节点的LP求解都花时间弱松弛直接导致全盘崩溃。第三层麻烦是数值稳定性。大规模模型往往由不同来源的数据拼成系数尺度参差不齐。有的约束系数是百万级Big-M有的是0.001的小数矩阵病态会让LP求解器产生大量数值警告甚至给出错误的最优解判定。这类问题在几千行约束时就开始冒头到大规模阶段会成为名副其实的拦路虎。这三种麻烦不是独立的经常同时出现。记住一点大规模MIP难难的不只是NP-hard而是松弛质量、数值质量、搜索策略三者的叠加效应。1.2 为什么默认参数常在大规模问题上失效商业或开源求解器默认参数适配的是一般情况背后的假设是模型本身比较规整。一旦进入大规模实战默认策略的问题就很明显默认的预处理开关通常会开启但不会针对你的模型定制遇到特殊结构时它不一定能挖到最深处。默认的割平面轮数有限根节点加几轮割就收手弱下界的模型依然弱。默认的启发式是通用型的可能迟迟找不到高质量整数解上界差导致搜索树很大。默认的并行策略要兼顾各种机器未必适应你手头只有有限核数的环境。我在模拟项目X中处理过一个数百列、数万行的大规模MIP实例直接丢给默认配置跑等了两个小时gap还在18%附近徘徊。后来从模型结构入手自己加了两个定制割平面并把一个启发式提前到根节点运行十分钟内gap就压到了3%以内。这不算什么惊天的算法创新只是把精确算法每个环节的潜力真正用起来。1.3 理解精确算法是调优的前提如果你只是把求解器当黑盒遇到性能问题就只能盲目调参数。但如果你理解了分支定界和分支切割的骨架就能判断当前卡住的地方到底是下界不够紧、上界不够好还是分支策略在偷懒又或者是数值问题导致收敛判断出错。针对性调优效率远高于无头苍蝇式尝试。接下来我从精确算法的主干讲起再逐个拆解预处理、割平面、启发式、分支策略和并行实现最后落到代码可以实现的程度。2. 精确算法的主干分支定界与分支切割为什么能保证最优2.1 分支定界框架的四个操作分支定界Branch and Bound是所有现代MIP求解器的算法骨架。理解它就理解了精确算法的运行方式。考虑标准形式min c^T x s.t. Ax b x_j ∈ Z, j ∈ I x_j 0, j ∈ C分支定界维护一棵搜索树。每个节点对应一个子问题通常是在原问题上额外施加若干变量边界。算法的四个基本操作如下求解松弛忽略整数约束求解该子问题的LP或更一般的凸松弛得到下界。剪枝判定如果该节点下界不低于当前全局上界说明这个子树里不可能有更好的解直接丢弃。整数判定如果LP松弛解恰好满足所有整数约束它就是一个可行整数解更新全局上界。分支否则选取一个违反整数约束的变量x_j将问题拆成x_j floor(x_j*)和x_j ceil(x_j*)两个子节点压入待处理队列。如果写成伪代码就是一个非常简洁的循环stack [root_node] UB 初始可行解找不到就用正无穷 while stack 非空: node pop(stack) LB solve_lp(node) if LB UB - epsilon: continue if is_integer_feasible(LB_solution): UB min(UB, obj(LB_solution)) elif 有割平面可加: 加入割平面重新求解节点 else: x_j choose_branch_variable(node) 左子 impose(x_j floor(x_j*)) 右子 impose(x_j ceil(x_j*)) push(left); push(right)这个循环的结束条件就是所有有效节点都被处理完毕。当队列为空时UB就是全局最优值因为任何可能更好的子树都已经被剪掉而剪枝依据都是可靠的下界。这就是精确算法和启发式的本质区别精确算法不但给出解还给出最优性的证明。2.2 分支切割在树里动态加不等式分支切割Branch and Cut本质上就是分支定界只是在每个节点上增加了割平面分离这一环节。求解器先求解LP松弛如果解是分数的尝试找一组线性不等式让这个分数解被排除但所有整数可行解都保留在这些不等式的一侧。然后把这些不等式加入当前节点的LP模型重新求解。为什么要这样做因为LP松弛往往太弱。以一个背包约束为例5x1 4x2 3x3 2x4 7, x为0/1LP松弛很容易给出一个分数线解比如x(1, 0.5, 0, 0)。一个有效的割平面可以把这类分数点切掉。加入割平面后节点松弛解更靠近整数可行域下界更紧分支树更小。在实现时割平面分离不是一次性完成的。求解器会循环求解LP - 检查解是否违反割平面族 - 找到违反的割就加 - 重新求解直到没有发现有效的割或者循环次数达到上限。这个过程通常称为分离循环。2.3 上界、下界和最优性证明分支定界的核心指标是gapgap (UB - LB) / UBUB是当前找到的最好整数解目标值LB是待处理节点下界的最小值。当gap0搜索树可以停止。理解这一点后你会发现优化MIP求解效率本质上只有三条路提高UB找更好的整数解、提高LB加割平面、改进松弛、减少节点数更聪明的分支和剪枝。后面几章讲的预处理、割平面、启发式最终都是在影响这三个指标之一。举个例子在模拟项目X的一个排班实例中根节点初始下界是4200而一个随机可行解给了上界5800gap高达27%。加入两层割平面后下界升到4800再用一个邻域启发式把上界拉到5100gap立刻缩小到6%以内。后续分支树几乎不用展开太多节点就能收工。3. 预处理很多求解时间是在搜索开始前省下来的3.1 预处理到底是干什么的预处理是精确算法中成本最低、收益却往往最高的环节。它不会改变可行域和目标函数等价性但会把模型改得更小、更紧、更稳定。预处理通常发生在求解器正式启动分支定界之前也可以在切割循环中途周期性触发。我在实际项目里见过最夸张的一个例子一个测试模型有几十万行约束预处理跑了不到两分钟把模型压缩到原来规模的65%后续LP求解速度几乎翻倍。那是模拟项目X里的一个组合块选择问题大量0/1变量之间存在隐含等价关系和逻辑蕴含预处理把这些关系自动挖出来了。3.2 常见预处理的分类与作用预处理技术大致分四类我整理成一张表类型核心思想典型操作冗余清理删除不影响问题的元素删除零系数变量、删除恒真/恒假约束、合并重复约束变量聚合减少变量个数发现x y 2的关系后消去其中一个变量域传播收紧变量取值范围利用约束推导x_j上/下界检测矛盾逻辑结构挖掘提取变量间逻辑关系构造蕴含图、冲突图记录成对互斥变量域传播值得多说一句。比如有个约束2a 3b 5c 4, a,b,c ∈ {0,1}预处理可以发现a和b不可能同时为1否则左边最小值是235已经超过4类似地b和c也不可能同时为1。这些成对互斥关系会被记录成冲突图后面分支时会优先选择冲突图上度数高的变量因为分支它们产生的剪枝效果最好。3.3 使用预处理的几个实操注意点预处理不是万能的使用时有几个坑。第一个坑自定义割平面和预处理的冲突。某些预处理变换会改变约束的隐含结构如果你在求解器里写死了一个基于原模型推导的割平面可能不再有效。稳妥的做法是把自定义割平面以惰性约束Lazy Constraint的形式注册而不是一次性全部预先加进模型。第二个坑数值病态模型预设的效果会被削弱。约束里如果有Big-M系数预处理阶段的bound tightening可能出问题甚至产生错误结论。这种情况下优先调整模型本身而不是指望预处理兜底。第三个坑对于实际耗时极短的模型预处理时间可能占比过高。几十万行约束的大规模模型预处理几分钟是正常的但如果模型本身半小时能跑完预处理五分钟也不算浪费相反只有一两千变量的小模型预处理花几秒都可能不值得可以关闭部分预处理选项。4. 割平面松弛太松是精确算法效率低下的根源4.1 为什么一定要有割平面如果只靠LP松弛和分支很多大规模MIP会变成一场灾难。因为LP松弛是连续问题的界而整数要求会砍掉可行域的大块体积。分支确实能把分数解排除掉但代价是节点数量指数增长。割平面则想得更直接与其通过分支无限细分不如先在整个可行域上得到更好的连续逼近。割平面的有效性在于它是对整数可行域有效不等式。一种理解方式把整数可行域做凸包其顶点就是可能的最优整数解候选。LP松弛的可行域大于这个凸包割平面就是一步步把松弛域推向凸包的边界。理论上给足够的割平面甚至可以在根节点直接解出整数问题的凸包顶点实践中虽然做不到但能极大减少分支数。4.2 常用的几类割平面现代求解器内置几十种割平面常见的有Gomory割从最优单纯形表的一个分数行直接代数推导通用性强几乎什么模型都能用但数值敏感度也高。混合整数舍入割MIR对单行混合整数约束做舍入分析适用范围广是许多通用割平面的基础。覆盖割Cover Cut专门针对0/1背包不等式从约束系数中找一组多选任何一个就超容量的覆盖集再推导不等式。冲突图割Clique Cut基于成对互斥变量的冲突图找出极大团生成团约束。SOS割配合SOS1约束使用针对一组变量至多一个非零的结构。割平面在实现时要考虑数值和计算成本。割平面分离器本身也要消耗时间如果每求解一次LP就要跑几十个分离器总耗时会非常可观。因此求解器会做轮次控制和有效性跟踪某个割长时间没能切掉新顶点就暂时进入休眠求解器还会周期性地从LP模型中删除多余割平面防止模型矩阵无限膨胀。4.3 分离循环的实操心得我自己的经验是面对一个根节点下界明显偏弱的模型可以先观察求解器的根节点日志如果每加入一轮割LP目标值就往上跳一块说明割平面还有潜力如果加了几轮后目标值几乎不动再继续加意义不大进入分支阶段更合适。在模拟项目X里我试过手动加一个定制覆盖割把某个测试实例的根节点下界从3120抬到3310分支节点数减少了约40%总求解时间却只快了一点点。原因是割平面分离本身消耗了不少LP求解时间算下来没有绝对优势。这个案例说明一个道理割平面不是越多越好要看每单位时间换来的下界提升是否划算。如果你要用求解器回调实现自定义割强烈建议分离阶段只返回明显违反的割不要返回边际有效的不等式。每条割都附带精确的稀疏系数避免大量填零项。用数值容忍度判断违反量比如违反量小于1e-6就跳过防止数值振荡。5. 上界从哪里来启发式在大规模精确求解里的地位5.1 精确算法里为什么还要启发式一个常见误解是既然做精确算法为什么还要用启发式答案很简单上界质量直接决定剪枝效率。如果UB非常差比如一个最小化问题当前最好解目标值是十万而下界只有五万那么搜索树里所有下界低于十万的节点都有潜力几乎没法剪枝。一旦用启发式找到一个目标值六万的好解树内大量下界超过六万的节点立刻被剪掉。从这个意义上说启发式不是为了近似求解而是为了给精确算法提供更好的剪枝上限。5.2 通用启发式的几种典型策略分支定界框架里常见的启发式包括LP舍入把LP松弛解中的分数变量按约束方向舍入再修复不可行性。目标动态惩罚禁忌搜索固定部分整数变量对剩余子问题做局部搜索。大邻域搜索LNS固定当前已解变量的大部分取值只放开一小部分变量作为子MIP求解试图改进现有解。RINS取当前LP解的目标变量值和历史整数解中取值一致的部分作为固定集合其余部分交给子MIP重优化。5.3 一个可以抄作业的RINS实现思路假设当前LP松弛给出了变量取值x_lp当前最优整数解是x_best。两者在某个变量x_j上取值相同说明这个变量在连续松弛和整数搜索方向上都倾向于同一个值大概率是可靠的。RINS的思路就是固定集合 F {j | x_lp[j] x_best[j]} 子问题 原问题 x_j x_lp[j] (∀j∈F) 设置子问题求解时限比如30秒 用子问题的解尝试更新全局UB在我的测试中这个简单策略在模拟项目X的中大规模实例上经常能找到不错的上界。它的优势是代价清晰、可控性强你控制的是子问题规模和时限而不是盲目搜索。实现时要注意子MIP本身也是一个MIP如果F太小子问题规模接近原问题就失去了意义。一般建议F覆盖至少60%-80%的整数变量。实践中可以动态调整F的比例。5.4 我的经验上界要抢不要等搜索早期尽快拿到一个可行解相当于先立住了剪枝的标杆。默认求解器当然也会跑启发式但针对你的模型结构写一个定制启发式往往能获得更早的上界。我通常在分支定界开始前先跑一个两分钟的定制启发式如果找到了好上界后面的搜索会轻松非常多。千万不要忽略上界的作用。有一次我调一个模型只改进了启发式策略没有动任何割平面和分支策略总求解时间直接降了三分之一。外人会觉得玄学懂的人知道上界一紧整棵搜索树都瘦了。6. 分支策略与数值鲁棒性大规模搜索的工程考验6.1 分支变量的选择强、伪、可靠分支定界每次都要选一个分数变量来分裂问题。变量选得好不好直接影响搜索树节点数。常见策略有三种最不可行分支选分数部分最接近0.5的变量简单但不一定高效。强分支对候选变量分别预求解两个子节点看谁的LP下界提升大选提升最大的。效果最好但代价高因为每个候选都要额外解LP。伪成本分支给每个变量维护一个分支后界提升平均值的统计量用统计量代替实际预求解。速度快但初期统计不准。可靠性分支综合强分支和伪成本变量被分支次数少时用强分支来积累数据次数多了切换到伪成本。这是现代求解器的主流选择。理解分支策略的意义在于你可以根据模型特点调整候选集。比如模型中有很多对称变量用默认分支策略会陷入大量对称子问题。这时候加入对称性检测或者对候选变量做随机扰动排序往往有奇效。6.2 节点选择顺序为什么重要节点队列里该先处理哪个节点也会影响整体效率界优先Best Bound优先处理下界最小的节点有助于快速提高全局LB缩小gap适合证明最优性。深度优先优先扎进子树深处更容易尽早找到整数可行解提高UB但LB提升慢。混合策略搜索早期用深度优先找上界中后期切换成界优先这是许多求解器的默认逻辑。在大规模MIP中纯深度优先容易在某一棵子树里钻牛角尖而纯界优先可能迟迟找不到好上界。观察求解器日志里的节点统计可以判断当前策略是否合适。如果节点数不多但gap下不去多半是UB不够好该调启发式如果节点数爆炸但LB有提升说明分支有效但上界拖后腿。6.3 数值鲁棒性最容易翻车的环节精确算法对数值极其敏感。LP求解器给出的是浮点解判断一个变量是否整数是基于容差的判断两个下界大小也是基于容差的。大规模病态模型会导致两种情况一是系数尺度悬殊。某约束里同时出现1e6和1e-6的系数单纯形法换基判据会被浮点误差淹没。一个稳定判据可能被抖动成不稳定判据导致求解过程震荡甚至返回不可行解。这类问题在Big-M建模里最为典型。二是约束冗余和线性相关。大规模模型里可能存在大量几乎线性相关的行矩阵的数值秩不稳定预处理和割平面都容易出错。尤其在使用自定义割平面时两条割可能在数值误差下变成互相矛盾导致求解器误判不可行。我在模拟项目X里曾经遇到一个案例所有变量都是0/1目标系数从1到500不等部分约束里有一个大M项等于50万。初始模型直接求解时根节点LP就报了模型数值警告分支后的子节点偶尔出现不可行误判。后来我把约束中的大M拆掉了换用指示约束和SOS约束来表示同一个逻辑关系数值警告消失求解时间也明显下降。6.4 建模时怎么避免数值灾难关于数值鲁棒性几条建模纪律比任何求解器参数都重要尽量避免Big-M如果必须用选择实际可行的最小M值不要拍脑袋留余量。对目标函数和约束系数做尺度归一尽量让非零系数落在1e-3到1e3之间。用区间信息把变量的bound拉紧不要留下理论上有限但实际巨大的退化界。避免在一个模型里混用多个数量级的epsilon阈值数值容差设置要在全局统一考虑。这些纪律在模型设计阶段投入时间远好过在求解阶段和数值问题搏斗。7. 并行与实现从单线程到多线程的加速逻辑7.1 并行分支定界的工作池模型大规模MIP的并行实现主流思路是工作池模型。搜索树节点放在一个共享队列中多个工作线程各自从队列取出节点独立求解LP、独立加割、独立分支把生成的子节点重新放回队列。听起来简单实现里有个关键点**全局UB是共享的。**一旦某个线程找到一个更好的整数解其它线程要能立刻读到压缩后的UB这样才能尽快剪掉自己手上没必要继续处理的节点。UPDATES靠共享内存里的原子操作或者使用锁保护的全局变量。但要注意UB更新太频繁会带来锁竞争开销。实践中会限制更新频率比如只在下界变化超过一定比例时才写回全局UB。我自己实现过一个简化版本用的是双缓冲原子读效果还凑合。7.2 负载均衡是并行的最大敌人并行分支定界有一个常见尴尬搜索树未必像我们期望的那样均匀分布。有些子树很快被剪掉有些子树异常庞大。如果一开始把节点按固定策略分发很容易出现部分线程空转、部分线程忙死。因此大规模实现里通常允许动态负载迁移空闲线程可以从繁忙线程那里偷节点。这听起来像操作系统的任务窃取调度本质上确实一个道理。不过节点在MIP里是包含分支记录和边界信息的轻量对象迁移成本很低麻烦的反而是LP子问题的环境准备。每个线程维护自己的LP求解器副本迁移节点时只需把当前节点的边界列表传过去不需要复制整个模型矩阵。7.3 并行加速比实测观察我基于测试实例做过并行加速实验结果如下线程数加速比说明11.0x基准42.9x负载尚可通信开销可控84.3x开始出现空转和重复割平面分离165.6x收益递减明显加速比不是线性的原因很多割平面分离本身是串行逻辑不同线程可能在相似节点上重复发现同一类割各线程还要各自加载LP求解器内存带宽成为瓶颈再加上搜索树本身的不确定性有些节点是不可并行的。实测里8到16线程是很多求解器的甜点区间再往上加核性价比就很低了。7.4 并行环境下的工程建议如果你自己写并行分支切割实现几个建议值得记录节点存储用紧凑格式只记录相对父节点的增量分支信息而不是每个节点都存全量LP模型。全局UB采用有界延迟广播不需要每次更新都同步所有线程。各线程独立跑启发式但发现可行解后要立即写入共享UB。割平面分离的结果可以缓存避免多个线程对相同子树反复计算相同割。这些细节对吞吐量的影响远超并行框架本身。最后分享一点我反复踩坑后总结的体会。处理大规模MIP时如果求解器卡住不要直接去调五花八门的参数先打开日志看看卡在哪个环节是根节点LP都解不出来还是gap一直不降还是数值警告频发还是并行扩展率上不去。定位到具体环节再去调整预处理、割平面、启发式或分支策略思路才会清晰。精确算法的实现本质上就是一场系统级的配合把每个部件都调到合适状态大规模问题才会从跑不动变成跑得动并且可证明最优。
做了这么多年运筹优化见过不少把MIP模型扔给求解器就撒手不管的情况。几十个变量的小问题默认参数确实能跑出结果可一旦变量数涨到几十万、上百万约束铺开几千甚至上万行黑盒求解器往往会暴露真实水平——要么根节点松弛解不出来要么上下界缩得很慢要么内存先爆掉。这篇文章想聊的就是大规模MIP的精确算法和实现层面的那些事分支定界为什么能保证最优分支切割、预处理、割平面、启发式各自承担什么职责以及工程实现里有哪些容易被忽略的细节。适合已经用过求解器、但想往更深一层走的同学也适合被大规模整数规划折磨过的从业者。1. 大规模MIP的难点在哪黑盒求解器的真实困境1.1 规模带来的三个层次麻烦MIP的数学形式不难理解在一组线性约束下让一部分变量取整数值极小化目标函数。可一旦投入实际应用规模带来的麻烦立刻变得具体。第一层麻烦是组合爆炸。假设有一个纯0/1问题只有50个0/1变量最坏情况下要遍历2的50次方种组合这个数字远超任何机器的枚举能力。即便求解器聪明的分支不会遍历全部组合整数变量个数只要超过几百个搜索空间就足够让朴素算法彻底崩溃。第二层麻烦是松弛太弱。求解器内部依赖LP松弛来获得下界如果模型里存在大量Big-M约束、弱线性松弛分数解会离整数解很远那么下界很低剪枝几乎不起作用分支树就会疯狂扩张。这个问题在小规模上不明显因为哪怕剪枝不高效反正问题小兜底也能跑完但大规模下每个节点的LP求解都花时间弱松弛直接导致全盘崩溃。第三层麻烦是数值稳定性。大规模模型往往由不同来源的数据拼成系数尺度参差不齐。有的约束系数是百万级Big-M有的是0.001的小数矩阵病态会让LP求解器产生大量数值警告甚至给出错误的最优解判定。这类问题在几千行约束时就开始冒头到大规模阶段会成为名副其实的拦路虎。这三种麻烦不是独立的经常同时出现。记住一点大规模MIP难难的不只是NP-hard而是松弛质量、数值质量、搜索策略三者的叠加效应。1.2 为什么默认参数常在大规模问题上失效商业或开源求解器默认参数适配的是一般情况背后的假设是模型本身比较规整。一旦进入大规模实战默认策略的问题就很明显默认的预处理开关通常会开启但不会针对你的模型定制遇到特殊结构时它不一定能挖到最深处。默认的割平面轮数有限根节点加几轮割就收手弱下界的模型依然弱。默认的启发式是通用型的可能迟迟找不到高质量整数解上界差导致搜索树很大。默认的并行策略要兼顾各种机器未必适应你手头只有有限核数的环境。我在模拟项目X中处理过一个数百列、数万行的大规模MIP实例直接丢给默认配置跑等了两个小时gap还在18%附近徘徊。后来从模型结构入手自己加了两个定制割平面并把一个启发式提前到根节点运行十分钟内gap就压到了3%以内。这不算什么惊天的算法创新只是把精确算法每个环节的潜力真正用起来。1.3 理解精确算法是调优的前提如果你只是把求解器当黑盒遇到性能问题就只能盲目调参数。但如果你理解了分支定界和分支切割的骨架就能判断当前卡住的地方到底是下界不够紧、上界不够好还是分支策略在偷懒又或者是数值问题导致收敛判断出错。针对性调优效率远高于无头苍蝇式尝试。接下来我从精确算法的主干讲起再逐个拆解预处理、割平面、启发式、分支策略和并行实现最后落到代码可以实现的程度。2. 精确算法的主干分支定界与分支切割为什么能保证最优2.1 分支定界框架的四个操作分支定界Branch and Bound是所有现代MIP求解器的算法骨架。理解它就理解了精确算法的运行方式。考虑标准形式min c^T x s.t. Ax b x_j ∈ Z, j ∈ I x_j 0, j ∈ C分支定界维护一棵搜索树。每个节点对应一个子问题通常是在原问题上额外施加若干变量边界。算法的四个基本操作如下求解松弛忽略整数约束求解该子问题的LP或更一般的凸松弛得到下界。剪枝判定如果该节点下界不低于当前全局上界说明这个子树里不可能有更好的解直接丢弃。整数判定如果LP松弛解恰好满足所有整数约束它就是一个可行整数解更新全局上界。分支否则选取一个违反整数约束的变量x_j将问题拆成x_j floor(x_j*)和x_j ceil(x_j*)两个子节点压入待处理队列。如果写成伪代码就是一个非常简洁的循环stack [root_node] UB 初始可行解找不到就用正无穷 while stack 非空: node pop(stack) LB solve_lp(node) if LB UB - epsilon: continue if is_integer_feasible(LB_solution): UB min(UB, obj(LB_solution)) elif 有割平面可加: 加入割平面重新求解节点 else: x_j choose_branch_variable(node) 左子 impose(x_j floor(x_j*)) 右子 impose(x_j ceil(x_j*)) push(left); push(right)这个循环的结束条件就是所有有效节点都被处理完毕。当队列为空时UB就是全局最优值因为任何可能更好的子树都已经被剪掉而剪枝依据都是可靠的下界。这就是精确算法和启发式的本质区别精确算法不但给出解还给出最优性的证明。2.2 分支切割在树里动态加不等式分支切割Branch and Cut本质上就是分支定界只是在每个节点上增加了割平面分离这一环节。求解器先求解LP松弛如果解是分数的尝试找一组线性不等式让这个分数解被排除但所有整数可行解都保留在这些不等式的一侧。然后把这些不等式加入当前节点的LP模型重新求解。为什么要这样做因为LP松弛往往太弱。以一个背包约束为例5x1 4x2 3x3 2x4 7, x为0/1LP松弛很容易给出一个分数线解比如x(1, 0.5, 0, 0)。一个有效的割平面可以把这类分数点切掉。加入割平面后节点松弛解更靠近整数可行域下界更紧分支树更小。在实现时割平面分离不是一次性完成的。求解器会循环求解LP - 检查解是否违反割平面族 - 找到违反的割就加 - 重新求解直到没有发现有效的割或者循环次数达到上限。这个过程通常称为分离循环。2.3 上界、下界和最优性证明分支定界的核心指标是gapgap (UB - LB) / UBUB是当前找到的最好整数解目标值LB是待处理节点下界的最小值。当gap0搜索树可以停止。理解这一点后你会发现优化MIP求解效率本质上只有三条路提高UB找更好的整数解、提高LB加割平面、改进松弛、减少节点数更聪明的分支和剪枝。后面几章讲的预处理、割平面、启发式最终都是在影响这三个指标之一。举个例子在模拟项目X的一个排班实例中根节点初始下界是4200而一个随机可行解给了上界5800gap高达27%。加入两层割平面后下界升到4800再用一个邻域启发式把上界拉到5100gap立刻缩小到6%以内。后续分支树几乎不用展开太多节点就能收工。3. 预处理很多求解时间是在搜索开始前省下来的3.1 预处理到底是干什么的预处理是精确算法中成本最低、收益却往往最高的环节。它不会改变可行域和目标函数等价性但会把模型改得更小、更紧、更稳定。预处理通常发生在求解器正式启动分支定界之前也可以在切割循环中途周期性触发。我在实际项目里见过最夸张的一个例子一个测试模型有几十万行约束预处理跑了不到两分钟把模型压缩到原来规模的65%后续LP求解速度几乎翻倍。那是模拟项目X里的一个组合块选择问题大量0/1变量之间存在隐含等价关系和逻辑蕴含预处理把这些关系自动挖出来了。3.2 常见预处理的分类与作用预处理技术大致分四类我整理成一张表类型核心思想典型操作冗余清理删除不影响问题的元素删除零系数变量、删除恒真/恒假约束、合并重复约束变量聚合减少变量个数发现x y 2的关系后消去其中一个变量域传播收紧变量取值范围利用约束推导x_j上/下界检测矛盾逻辑结构挖掘提取变量间逻辑关系构造蕴含图、冲突图记录成对互斥变量域传播值得多说一句。比如有个约束2a 3b 5c 4, a,b,c ∈ {0,1}预处理可以发现a和b不可能同时为1否则左边最小值是235已经超过4类似地b和c也不可能同时为1。这些成对互斥关系会被记录成冲突图后面分支时会优先选择冲突图上度数高的变量因为分支它们产生的剪枝效果最好。3.3 使用预处理的几个实操注意点预处理不是万能的使用时有几个坑。第一个坑自定义割平面和预处理的冲突。某些预处理变换会改变约束的隐含结构如果你在求解器里写死了一个基于原模型推导的割平面可能不再有效。稳妥的做法是把自定义割平面以惰性约束Lazy Constraint的形式注册而不是一次性全部预先加进模型。第二个坑数值病态模型预设的效果会被削弱。约束里如果有Big-M系数预处理阶段的bound tightening可能出问题甚至产生错误结论。这种情况下优先调整模型本身而不是指望预处理兜底。第三个坑对于实际耗时极短的模型预处理时间可能占比过高。几十万行约束的大规模模型预处理几分钟是正常的但如果模型本身半小时能跑完预处理五分钟也不算浪费相反只有一两千变量的小模型预处理花几秒都可能不值得可以关闭部分预处理选项。4. 割平面松弛太松是精确算法效率低下的根源4.1 为什么一定要有割平面如果只靠LP松弛和分支很多大规模MIP会变成一场灾难。因为LP松弛是连续问题的界而整数要求会砍掉可行域的大块体积。分支确实能把分数解排除掉但代价是节点数量指数增长。割平面则想得更直接与其通过分支无限细分不如先在整个可行域上得到更好的连续逼近。割平面的有效性在于它是对整数可行域有效不等式。一种理解方式把整数可行域做凸包其顶点就是可能的最优整数解候选。LP松弛的可行域大于这个凸包割平面就是一步步把松弛域推向凸包的边界。理论上给足够的割平面甚至可以在根节点直接解出整数问题的凸包顶点实践中虽然做不到但能极大减少分支数。4.2 常用的几类割平面现代求解器内置几十种割平面常见的有Gomory割从最优单纯形表的一个分数行直接代数推导通用性强几乎什么模型都能用但数值敏感度也高。混合整数舍入割MIR对单行混合整数约束做舍入分析适用范围广是许多通用割平面的基础。覆盖割Cover Cut专门针对0/1背包不等式从约束系数中找一组多选任何一个就超容量的覆盖集再推导不等式。冲突图割Clique Cut基于成对互斥变量的冲突图找出极大团生成团约束。SOS割配合SOS1约束使用针对一组变量至多一个非零的结构。割平面在实现时要考虑数值和计算成本。割平面分离器本身也要消耗时间如果每求解一次LP就要跑几十个分离器总耗时会非常可观。因此求解器会做轮次控制和有效性跟踪某个割长时间没能切掉新顶点就暂时进入休眠求解器还会周期性地从LP模型中删除多余割平面防止模型矩阵无限膨胀。4.3 分离循环的实操心得我自己的经验是面对一个根节点下界明显偏弱的模型可以先观察求解器的根节点日志如果每加入一轮割LP目标值就往上跳一块说明割平面还有潜力如果加了几轮后目标值几乎不动再继续加意义不大进入分支阶段更合适。在模拟项目X里我试过手动加一个定制覆盖割把某个测试实例的根节点下界从3120抬到3310分支节点数减少了约40%总求解时间却只快了一点点。原因是割平面分离本身消耗了不少LP求解时间算下来没有绝对优势。这个案例说明一个道理割平面不是越多越好要看每单位时间换来的下界提升是否划算。如果你要用求解器回调实现自定义割强烈建议分离阶段只返回明显违反的割不要返回边际有效的不等式。每条割都附带精确的稀疏系数避免大量填零项。用数值容忍度判断违反量比如违反量小于1e-6就跳过防止数值振荡。5. 上界从哪里来启发式在大规模精确求解里的地位5.1 精确算法里为什么还要启发式一个常见误解是既然做精确算法为什么还要用启发式答案很简单上界质量直接决定剪枝效率。如果UB非常差比如一个最小化问题当前最好解目标值是十万而下界只有五万那么搜索树里所有下界低于十万的节点都有潜力几乎没法剪枝。一旦用启发式找到一个目标值六万的好解树内大量下界超过六万的节点立刻被剪掉。从这个意义上说启发式不是为了近似求解而是为了给精确算法提供更好的剪枝上限。5.2 通用启发式的几种典型策略分支定界框架里常见的启发式包括LP舍入把LP松弛解中的分数变量按约束方向舍入再修复不可行性。目标动态惩罚禁忌搜索固定部分整数变量对剩余子问题做局部搜索。大邻域搜索LNS固定当前已解变量的大部分取值只放开一小部分变量作为子MIP求解试图改进现有解。RINS取当前LP解的目标变量值和历史整数解中取值一致的部分作为固定集合其余部分交给子MIP重优化。5.3 一个可以抄作业的RINS实现思路假设当前LP松弛给出了变量取值x_lp当前最优整数解是x_best。两者在某个变量x_j上取值相同说明这个变量在连续松弛和整数搜索方向上都倾向于同一个值大概率是可靠的。RINS的思路就是固定集合 F {j | x_lp[j] x_best[j]} 子问题 原问题 x_j x_lp[j] (∀j∈F) 设置子问题求解时限比如30秒 用子问题的解尝试更新全局UB在我的测试中这个简单策略在模拟项目X的中大规模实例上经常能找到不错的上界。它的优势是代价清晰、可控性强你控制的是子问题规模和时限而不是盲目搜索。实现时要注意子MIP本身也是一个MIP如果F太小子问题规模接近原问题就失去了意义。一般建议F覆盖至少60%-80%的整数变量。实践中可以动态调整F的比例。5.4 我的经验上界要抢不要等搜索早期尽快拿到一个可行解相当于先立住了剪枝的标杆。默认求解器当然也会跑启发式但针对你的模型结构写一个定制启发式往往能获得更早的上界。我通常在分支定界开始前先跑一个两分钟的定制启发式如果找到了好上界后面的搜索会轻松非常多。千万不要忽略上界的作用。有一次我调一个模型只改进了启发式策略没有动任何割平面和分支策略总求解时间直接降了三分之一。外人会觉得玄学懂的人知道上界一紧整棵搜索树都瘦了。6. 分支策略与数值鲁棒性大规模搜索的工程考验6.1 分支变量的选择强、伪、可靠分支定界每次都要选一个分数变量来分裂问题。变量选得好不好直接影响搜索树节点数。常见策略有三种最不可行分支选分数部分最接近0.5的变量简单但不一定高效。强分支对候选变量分别预求解两个子节点看谁的LP下界提升大选提升最大的。效果最好但代价高因为每个候选都要额外解LP。伪成本分支给每个变量维护一个分支后界提升平均值的统计量用统计量代替实际预求解。速度快但初期统计不准。可靠性分支综合强分支和伪成本变量被分支次数少时用强分支来积累数据次数多了切换到伪成本。这是现代求解器的主流选择。理解分支策略的意义在于你可以根据模型特点调整候选集。比如模型中有很多对称变量用默认分支策略会陷入大量对称子问题。这时候加入对称性检测或者对候选变量做随机扰动排序往往有奇效。6.2 节点选择顺序为什么重要节点队列里该先处理哪个节点也会影响整体效率界优先Best Bound优先处理下界最小的节点有助于快速提高全局LB缩小gap适合证明最优性。深度优先优先扎进子树深处更容易尽早找到整数可行解提高UB但LB提升慢。混合策略搜索早期用深度优先找上界中后期切换成界优先这是许多求解器的默认逻辑。在大规模MIP中纯深度优先容易在某一棵子树里钻牛角尖而纯界优先可能迟迟找不到好上界。观察求解器日志里的节点统计可以判断当前策略是否合适。如果节点数不多但gap下不去多半是UB不够好该调启发式如果节点数爆炸但LB有提升说明分支有效但上界拖后腿。6.3 数值鲁棒性最容易翻车的环节精确算法对数值极其敏感。LP求解器给出的是浮点解判断一个变量是否整数是基于容差的判断两个下界大小也是基于容差的。大规模病态模型会导致两种情况一是系数尺度悬殊。某约束里同时出现1e6和1e-6的系数单纯形法换基判据会被浮点误差淹没。一个稳定判据可能被抖动成不稳定判据导致求解过程震荡甚至返回不可行解。这类问题在Big-M建模里最为典型。二是约束冗余和线性相关。大规模模型里可能存在大量几乎线性相关的行矩阵的数值秩不稳定预处理和割平面都容易出错。尤其在使用自定义割平面时两条割可能在数值误差下变成互相矛盾导致求解器误判不可行。我在模拟项目X里曾经遇到一个案例所有变量都是0/1目标系数从1到500不等部分约束里有一个大M项等于50万。初始模型直接求解时根节点LP就报了模型数值警告分支后的子节点偶尔出现不可行误判。后来我把约束中的大M拆掉了换用指示约束和SOS约束来表示同一个逻辑关系数值警告消失求解时间也明显下降。6.4 建模时怎么避免数值灾难关于数值鲁棒性几条建模纪律比任何求解器参数都重要尽量避免Big-M如果必须用选择实际可行的最小M值不要拍脑袋留余量。对目标函数和约束系数做尺度归一尽量让非零系数落在1e-3到1e3之间。用区间信息把变量的bound拉紧不要留下理论上有限但实际巨大的退化界。避免在一个模型里混用多个数量级的epsilon阈值数值容差设置要在全局统一考虑。这些纪律在模型设计阶段投入时间远好过在求解阶段和数值问题搏斗。7. 并行与实现从单线程到多线程的加速逻辑7.1 并行分支定界的工作池模型大规模MIP的并行实现主流思路是工作池模型。搜索树节点放在一个共享队列中多个工作线程各自从队列取出节点独立求解LP、独立加割、独立分支把生成的子节点重新放回队列。听起来简单实现里有个关键点**全局UB是共享的。**一旦某个线程找到一个更好的整数解其它线程要能立刻读到压缩后的UB这样才能尽快剪掉自己手上没必要继续处理的节点。UPDATES靠共享内存里的原子操作或者使用锁保护的全局变量。但要注意UB更新太频繁会带来锁竞争开销。实践中会限制更新频率比如只在下界变化超过一定比例时才写回全局UB。我自己实现过一个简化版本用的是双缓冲原子读效果还凑合。7.2 负载均衡是并行的最大敌人并行分支定界有一个常见尴尬搜索树未必像我们期望的那样均匀分布。有些子树很快被剪掉有些子树异常庞大。如果一开始把节点按固定策略分发很容易出现部分线程空转、部分线程忙死。因此大规模实现里通常允许动态负载迁移空闲线程可以从繁忙线程那里偷节点。这听起来像操作系统的任务窃取调度本质上确实一个道理。不过节点在MIP里是包含分支记录和边界信息的轻量对象迁移成本很低麻烦的反而是LP子问题的环境准备。每个线程维护自己的LP求解器副本迁移节点时只需把当前节点的边界列表传过去不需要复制整个模型矩阵。7.3 并行加速比实测观察我基于测试实例做过并行加速实验结果如下线程数加速比说明11.0x基准42.9x负载尚可通信开销可控84.3x开始出现空转和重复割平面分离165.6x收益递减明显加速比不是线性的原因很多割平面分离本身是串行逻辑不同线程可能在相似节点上重复发现同一类割各线程还要各自加载LP求解器内存带宽成为瓶颈再加上搜索树本身的不确定性有些节点是不可并行的。实测里8到16线程是很多求解器的甜点区间再往上加核性价比就很低了。7.4 并行环境下的工程建议如果你自己写并行分支切割实现几个建议值得记录节点存储用紧凑格式只记录相对父节点的增量分支信息而不是每个节点都存全量LP模型。全局UB采用有界延迟广播不需要每次更新都同步所有线程。各线程独立跑启发式但发现可行解后要立即写入共享UB。割平面分离的结果可以缓存避免多个线程对相同子树反复计算相同割。这些细节对吞吐量的影响远超并行框架本身。最后分享一点我反复踩坑后总结的体会。处理大规模MIP时如果求解器卡住不要直接去调五花八门的参数先打开日志看看卡在哪个环节是根节点LP都解不出来还是gap一直不降还是数值警告频发还是并行扩展率上不去。定位到具体环节再去调整预处理、割平面、启发式或分支策略思路才会清晰。精确算法的实现本质上就是一场系统级的配合把每个部件都调到合适状态大规模问题才会从跑不动变成跑得动并且可证明最优。
实现：从slack优化到BFS版完整模板)
的KM算法BFS模板：从顶标到增广全解析)
