有段时间我特别怕收到那种消息“帮个忙就三十来个订单六台车客户还有时间窗你排一下呗。”听起来是个小事真动手才发现三十个订单的全排列是 30!约等于 2.65×10³²就算给我一台每秒算十亿次的机器从宇宙大爆炸排到今天也排不完。这就是组合优化问题的典型面貌问题规模看着不大可行解的数量却像开了挂一样膨胀而你还得在这么多可能性里挑出代价最小的那一个。这篇是我在带课程第二章第一节标题就叫“2-1 组合优化问题”时整理的一份笔记也是我自己做排产、路径规划、资源分配这些年踩出来的经验汇总。它不讲纯数学证明讲的是组合优化到底是什么、为什么难、工业现场怎么建模、求解器怎么选、以及哪些地方最容易翻车。如果你刚开始接触运筹优化或者做过几年业务系统但对“为什么算法跑不出来”一直没搞明白这篇应该能帮你把整条链路串起来。1. 组合优化到底在解什么1.1 决策变量的离散性是分水岭判断一个问题是不是组合优化最省事的办法是看决策变量能不能连续取值。连续的问题比如“这台机器开多大功率”“这一炉温度控制在多少度”变量在区间里随便取值那是连续优化梯度下降、内点法这类方法就能上场。而组合优化里变量通常是“选不选这台机器”“走不走这条边”“这个人排不排这个班”取值只能是 0 或 1或者某个整数编号中间的过渡状态压根不存在。这个区别带来的后果比想象中大得多。连续函数在局部是平滑的你可以顺着斜率往下走走错了还能退回来离散的可行域是一堆散落的点点与点之间什么都没有你没法“沿着斜率走”只能一个一个去试或者用某种规则跳着找。整数规划里最麻烦的就是这种“看不见地形”的特性——求解器不会告诉你“往左一点会更好”它只能告诉你“左边那个点在不在可行域里”。还有一个容易被忽略的点变量离散之后,约束的拓扑结构变得极其重要。同样是一百个 0-1 变量如果约束是“总和不超过某个值”问题可能十毫秒就解完了如果约束里出现了成对关系、顺序关系、时间不重叠关系难度立刻上一个台阶。我带人做项目时看到有人把复杂的顺序约束硬塞进一个大不等式里通常一眼就知道后面会出事。1.2 目标函数和约束谁说了算新手最容易犯的错是把目标函数当成最重要的东西花大量时间调权重却忽略了约束才是决定求解难度的核心。目标函数只影响“往哪个方向找”约束划定的是“哪里能站人”。可行域的形状一旦变得又窄又碎求解器找可行解本身就要花掉绝大部分时间目标值好不好反而成了次要矛盾。举个实际的例子。做车辆调度时“每辆车载重不超过 8 吨”是典型的能力约束好处理但“客户 B 必须在客户 A 之后 30 分钟到 90 分钟之间被访问”这种时间窗加序约束会把可行域切得极其零碎。我做过一轮统计同一个 25 客户的小规模实例去掉时间窗部分求解耗时不到 1 秒加上时间窗之后同一台机器跑了 8 分钟还没收敛到 1% 的 gap。所以建模阶段有个很实用的判断原则先把约束按“是否制造可行域碎片”分类。总量型、容量型约束通常温和序关系、互斥关系、时间重叠关系通常凶悍。分类完再决定哪些约束必须硬性满足哪些可以放宽成软约束进目标函数。这一步做不做直接决定了后面要不要换算法。1.3 什么时候该上模型什么时候别碰不是所有“看起来像优化”的问题都值得建模求解。我个人的经验判断线有三条满足其中两条以上才值得动手规模会持续增长今天 30 个订单明年 300 个、约束会频繁变化客户加时间窗、车辆加跨区限制、人工排出来的方案有明显可优化空间比如空驶率常年在 30% 以上。反过来说如果一个场景订单量常年不超过 15 个约束三年没变过经验丰富的调度员五分钟就能排出八九不离十的方案那上模型的收益大概率覆盖不了维护成本。求解器再好也要人来维护数据接口、处理异常、解释结果这些隐性成本新手基本不会算进去。还有一种情况要特别警惕问题本身没定义清楚。我遇到过项目业务方说“我们要最优解”追问下去发现“最优”其实指“司机别太累、客户别投诉、油耗别太高”三个目标没有优先级也没有量化口径。这种时候正确的做法是先花两周把评价口径统一而不是急着写代码。2. 那些反复出现的经典问题原型组合优化有个好玩的地方无论行业怎么变最后都会归到有限的几个原型上。带过几个项目之后你会发现所谓“新问题”绝大多数是经典原型的变体。认得原型就能直接借用几十年的研究成果不用从零想算法。2.1 背包、指派、最短路三个最基础的原型0-1 背包问题是所有“选或不选、总资源有限”场景的抽象。变量是一组 0-1 变量 x_i目标最大化价值总和约束是重量总和不超过容量。听起来简单但它已经是 NP-hard 的——二十个物品有 2²⁰ 种组合四十个就是一万亿。实际业务里的预算分配、投资组合中“投不投这个标的”、仓库选址中“开不开这个仓”本质都是背包或者多重背包。指派问题处理的是“谁去做哪件事”的匹配关系变量是 x_ij 表示第 i 个人做第 j 件事约束是每行每列和都为 1。它的特殊之处在于约束矩阵是全幺模的用线性规划松弛之后解出来天然就是整数所以指派问题多项式时间可解几百个规模秒出结果。匈牙利算法就是干这个的。但一旦加上“一个人最多做两件事”“某些任务必须由持证人员做”这类额外约束幺模性被破坏问题立刻掉进 NP-hard。最短路问题是最容易被低估的一个。Dijkstra、Bellman-Ford 这些算法几乎是计算机专业的基础课但实际场景里的“带资源约束最短路”比如电动车续航有限、司机连续驾驶时间有限就不再是多形式的了必须上带状态的标号法或者直接建整数规划模型。这三个原型的价值在于它们构成了后面所有复杂问题的积木。VRP 是 TSP 加了容量和数量约束排产可以拆成若干个带优先级的指派网络设计可以看成带固定成本的背包叠加最短路。2.2 TSP 与 VRP路径类问题的统一视角旅行商问题TSP的表述人尽皆知走遍所有城市回到起点总路程最短。它的经典解法体系非常值得学因为后面所有路径问题都在复用这套思路。基础的建模用 MTZ 约束Miller-Tucker-Zemlin消除子回路效果一般但简单更强的是割平面法通过不断加入“子集割”把松弛解里的子回路切掉工程上最实用的还是2-opt / 3-opt / Or-opt 的局部搜索配合邻域限制和大邻域搜索LNS几千个点的实例也能在分钟级找到接近最优的解。VRP车辆路径问题就是把 TSP 加上“多辆车、每车容量有限、可能有时间窗”。它在学术上有几十个变体带时间窗的 VRPTW、带取送的 PDPTW、带多车场的 MDVRP 等等。我的建议是不要一上来就啃变体文献先把基础 CVRP 的模型跑通再逐个叠加约束每次加一个都重新测一遍求解时间。我见过太多项目一次性把所有业务约束堆进模型结果求解器直接不收敛最后只能推翻重来。2.3 排产、装箱、集合覆盖车间和后台的高频问题车间排产Job Shop / Flow Shop的核心是“工序之间不能重叠、工序之间有先后”。它的建模通常用区间变量加 NoOverlap 约束CP-SAT 这类基于约束规划的求解器比传统整数规划更擅长处理它。装箱问题Bin Packing是“把物品塞进尽量少的箱子”物流装车、服务器资源调度、集装箱配载都是它。集合覆盖Set Cover则是“用最少的集合覆盖所有元素”基站选址、消防站布局、测试用例最小化都是它的应用。下面这张表是我自己整理的对照表做需求评审的时候拿出来对一遍基本能定位到该用哪个原型经典原型决策变量核心约束常见业务映射0-1 背包选不选某对象资源总量上限预算分配、选址、投资组合指派问题谁做哪件事行列互斥为 1人员分派、设备分配、任务匹配带资源最短路走不走某条边路径连续 资源消耗电动车路径、驾驶时长限制TSP / VRP访问顺序每个点访问一次 容量/时间窗配送、巡检、上门服务排程车间排产工序起止时间机器不重叠 工序先后生产线排产、工序调度装箱问题物品放哪个箱箱子容量装车配载、容器调度集合覆盖选不选某个设施元素至少被覆盖一次基站选址、网点布局、用例精简表格看着简单但我要强调一句真实业务几乎从来不是单一原型而是两三个原型的叠加。比如“上门服务排程”实际是带时间窗的指派问题加上路径问题——先决定哪个师傅接哪几单再决定每单的先后顺序。这种情况下分两层建模、分层求解通常比强行揉成一个大模型效果更好。3. 难度到底从哪来3.1 组合爆炸的量化感受我习惯用一组数字给学生建立直觉。10 个城市的 TSP可能的巡回数是 (10-1)!/2 181440随手就能穷举。15 个城市是 4.36×10¹⁰个人电脑穷举要跑好几个小时。20 个城市是 6.08×10¹⁶按每秒检查一亿条路径算需要将近 20 年。到了 30 个城市这个数字大到已经没有物理意义了。背包也是一样。0-1 背包的搜索空间是 2ⁿ。n30 是十亿级别还能硬扛n50 是一千万亿级别暴力法彻底没戏n100 就是 1.27×10³⁰比地球上的沙子还多。关键在于规模每增加 10 个物品搜索空间就乘以 1024这个增长速度远超任何硬件升级速度。这就是为什么所有实用算法都在做同一件事想尽办法不去枚举全部解。分支定界靠的是“这个子问题的下界已经比当前最优解差了整枝剪掉”动态规划靠的是“不同路径到达同一状态后后续完全等价可以合并”启发式靠的是“只在一个有希望的邻域里搜索”。三种思路本质上都是在砍搜索树。3.2 NP-hard 在工程上的真实含义很多人对 NP-hard 有个误解以为意味着“绝对解不出来”。其实它的准确含义是目前没有已知的多项式时间精确算法而且如果某一个 NP-hard 问题找到了多项式算法那所有 NP 问题都找到了。它说明的是问题难度的下限不是“你的实例一定解不动”。工程实践中真正重要的是你的实例落在哪个区间。我按经验把实例分成四档小规模变量 100 且约束简单精确算法秒解直接上求解器。中等规模变量 100~10000精确算法能给出带 gap 的解30 秒到几分钟不等通常够用。大规模变量 10⁴~10⁶精确算法基本放弃靠启发式或者“分解组合”。超大规模变量 10⁶必须做问题特定的结构利用通用求解器顶不住。分档的变量阈值不是绝对的强依赖约束结构。同样是 500 个 0-1 变量的背包求解器可能 0.1 秒搞定但 500 个变量的二次指派问题QAP可能跑一小时还在 gap 50% 附近晃悠。3.3 LP 松弛与整数间隙判断一个模型“紧不紧”最直接的指标是整数间隙integrality gap也就是最优整数解和 LP 松弛最优解之间的相对差距。LP 松弛就是把所有“必须是整数”的要求去掉变成连续线性规划它能快速求解同时给出原问题的一个下界最小化问题时。间隙越小说明 LP 松弛给出的“乐观估计”越接近真实情况求解器剪枝就越狠。集合覆盖的 LP 松弛间隙可以做到 ln(n) 级别而某些图着色或者二次问题间隙能大到几倍甚至几十倍。我调模型的时候有个习惯每次加完约束先把 LP 松弛解打出来看。如果松弛解里一大堆 0.5、0.3 这种“半吊子”值说明这版模型松得厉害得想办法加割平面或者改写法。有个具体的技巧分享如果松弛解里出现大量分数值可以试试加“整数性提升约束”比如对某组互斥变量显式声明和不超过 1或者对总量约束补一个“至少”方向的下界。这些约束在整数解上都是冗余的但能显著收紧松弛有时候效果比调求解器参数好得多。4. 精确解还是近似解怎么选4.1 精确算法的三条主线分支定界Branch and Bound是现代整数规划求解器的骨架。思路是先解 LP 松弛如果解已经是整数就结束否则选一个分数变量分支成“0”和“1”两个子问题递归下去用下界剪枝。它的效率高度依赖下界的紧度和分支变量的选择策略。Gurobi、CPLEX、SCIP 这些商业或开源求解器本质上都是分支定界加上大量预处理、割平面、启发式把一棵巨大的搜索树砍到能跑完。割平面法是往模型里动态添加“切掉分数解但不切掉任何整数解”的新约束。经典的 Gomory 割、覆盖割、Clique 割都属于这类。手工写割平面的人不多但理解它的思想很重要——它解释了为什么求解器有时候跑到一半会突然报“添加了 xx 个割”。动态规划在背包、最短路、序列决策这些问题上效率极高前提是状态能压缩。比如背包的 DP 状态是“前 i 个物品、容量 j”状态数是 n×C只要容量不是天文数字就能算。4.2 启发式与元启发式为什么它们在实际项目里更常见精确算法保证最优但代价是时间不可控。业务系统往往有硬性时间预算——用户点一下按钮八秒内必须出结果。这时候启发式就成了主力。贪心构造按某种规则排序后逐个决策。TSP 里最近邻法、背包里按价值密度排序都是。速度极快解质量一般但是绝佳的初始解几乎所有局部搜索都从贪心解出发。局部搜索2-opt / 3-opt / Or-opt在当前解附近做小改动只接受变好的改动。实现简单效果立竿见影缺点是容易卡在局部最优。模拟退火 / 禁忌搜索允许接受变差的解来跳出局部最优。模拟退火靠温度参数控制“接受坏解的概率”禁忌搜索靠一个短期记忆表禁止走回头路。这两个我在实际项目里用得最多。大邻域搜索LNS / ALNS每次破坏掉解的一部分比如删掉 20% 的客户再重新插入构造。ALNS 额外让多个破坏算子和修复算子按历史表现动态调整权重。这是目前 VRP 类问题上最实用的框架。遗传算法 / 蚁群算法群体智能类方法适合解空间极其复杂、目标函数不规则的场景。调参比较玄学我一般放在最后考虑。4.3 一张选型表和推进节奏场景特征推荐路线典型工具变量几百以内要最优解整数规划 / CP-SATOR-Tools CP-SAT、SCIP变量上千可接受 1%~3% gap商用求解器 时间上限Gurobi、CPLEX大规模路径问题ALNS / LNS 局部搜索自研框架、LKH排产调度类约束规划OR-Tools CP-SAT超大规模型组合分解 启发式自研按结构定制需要快速原型验证建模式语言PuLP、Pyomo推进节奏上我有个固定的四步法先用 PuLP 或 OR-Tools 把模型写成最简单版本只用小规模数据验证正确性然后逐步加真实约束每加一条记录求解时间接着确定时间预算选精确还是启发式最后再做工程优化热启动、增量求解、并行。跳过第一步直接上启发式是新手最常犯的错误——你连最优解长什么样都不知道怎么判断启发式解得好不好。5. 一个排产实例的完整建模推演理论说完了拿个具体问题走一遍。场景一个车间有 2 台并行机器4 个工件每个工件的加工时长已知每个工件只能在一台机器上加工一次且不可中断目标是最小化最大完工时间makespan。规模很小但足够把建模的每一个决策点讲清楚。5.1 从业务语言到决策变量业务语言是“哪个工件在哪台机器上做、从什么时候开始做”。翻译成数学变量需要三组每台机器上每个工件的开工时刻s[j,m]取整数范围 0 到时间上限每个工件在每个机器上的是否分配p[j,m]0-1 变量由 s 和加工时长推导出的区间变量interval[j,m]这个区间只在 p[j,m]1 时“存在”。这三组变量里区间变量是最关键的抽象。用普通的线性约束也能表达“两个任务不能重叠”但写法是“s_a d_a ≤ s_b 或 s_b d_b ≤ s_a”这种析取式需要引入大 M 变成混合整数约束不仅难看松弛还特别松。用区间变量加NoOverlap约束求解器内部会做专门的传播和检测效率和可读性都高一个档次。这里有个经验只要问题里出现“资源在时间上不能重叠”优先考虑约束规划风格的建模别硬凹成纯线性。OR-Tools 的 CP-SAT 在这一点上的优势非常明显我做过对比同样的排产实例CP-SAT 建模的解通常比手工写大 M 的整数模型快三到十倍。5.2 大 M 法、线性化与模型松紧度如果非要用线性模型大 M 是绕不开的。比如“工件 j 在机器 m 上加工”和“机器 m 在 t 时刻只能处理一个工件”之间的关系常用写法是s[j2] s[j1] d[j1] - M * (1 - y)其中 y 是 0-1 变量表示 j1 是否排在 j2 前面M 是一个“足够大”的常数。这里的 M 取值是个大坑。M 太大LP 松弛会变得极其宽松求解器剪枝困难还容易引发数值问题M 太小约束会失效解出来的方案根本不可行。我的做法是用变量的真实上界代替拍脑袋的 M。比如上面这个约束M 的合理取值是horizon - d[j1]而不是随便写个 100000。还有个小技巧如果能在预处理阶段算出一个更紧的时间上界比如所有工件总时长一定用它模型会紧不少。另一个高频需求是线性化乘积项。比如成本写成“是否分配 × 分配顺序”的乘积这就是非线性的。标准做法是引入辅助变量 z x·y加三条约束把它夹住z ≤ xz ≤ yz ≥ x y - 1。这个技巧不复杂但很多人写了半天没意识到自己写了个非线性模型然后奇怪求解器为什么报错。5.3 求解器不收敛时先查这三件事第一对称性。并行机器之间是完全对称的——把机器 1 和机器 2 的方案整体对调目标值一样。这种对称会让搜索树的规模直接乘以 m!m 是机器数求解器要反复证明“这两个镜像解等价”。解决办法是加对称破缺约束最常用的是字典序约束强制工件编号小的优先分配给小序号机器形式是p[j, m] sum(p[j, m] for j j, m m)这类写法。加了之后我的实测数据是求解时间下降 4 到 20 倍不等规模越大收益越明显。第二数值尺度。求解器的默认容差是 1e-6 量级。如果模型里某些系数是 0.001另一些是 1000000跨度超过 10¹²浮点运算就会出问题表现为“求解器说找到了解但检查发现约束违反了”。我的做法是统一量纲让所有系数落在 1e-3 到 1e6 之间。第三目标函数的权重。多目标加权求和的时候如果两个目标的量级差了几个数量级大的那个会完全压过小的。先做归一化或者用分层求解先优化主目标再把主目标固定成约束优化次目标比调权重靠谱得多。5.4 代码起手式下面这段是上面那个排产实例的 CP-SAT 实现可以直接跑from ortools.sat.python import cp_model jobs {J1: 12, J2: 25, J3: 18, J4: 9} machines 2 horizon sum(jobs.values()) # 用真实上界不要拍脑袋写大数 model cp_model.CpModel() intervals, ends {}, {} for m in range(machines): for j, dur in jobs.items(): s model.NewIntVar(0, horizon, fs_{j}_{m}) e model.NewIntVar(0, horizon, fe_{j}_{m}) present model.NewBoolVar(fp_{j}_{m}) intervals[j, m] model.NewOptionalIntervalVar( s, dur, e, present, fitv_{j}_{m}) ends[j, m] e # 同一台机器上的任务时间不能重叠 model.AddNoOverlap([intervals[j, m] for j in jobs]) # 每个工件只能选一台机器 for j in jobs: model.AddExactlyOne(intervals[j, m] for m in range(machines)) makespan model.NewIntVar(0, horizon, makespan) model.AddMaxEquality(makespan, list(ends.values())) model.Minimize(makespan) solver cp_model.CpSolver() solver.parameters.max_time_in_seconds 10 solver.parameters.relative_gap_limit 0.01 status solver.Solve(model) print(solver.StatusName(status), solver.ObjectiveValue())两个参数值得单独说。max_time_in_seconds给了硬性时间上限超时就返回当前最好解这在业务系统里比“一定求最优”重要得多。relative_gap_limit是提前收工的开关gap 小于 1% 就停对绝大多数业务场景这个精度完全够用而它能省掉大量用来“证明最优”的时间。如果做的是 TSP 类的路径问题启发式那套更顺手def two_opt(tour, dist, max_pass200): best, improved, p tour[:], True, 0 while improved and p max_pass: improved, p False, p 1 for i in range(1, len(best) - 1): for k in range(i 1, len(best)): a, b best[i - 1], best[i] c, d best[k], best[(k 1) % len(best)] if dist[a][c] dist[b][d] dist[a][b] dist[c][d]: best[i:k 1] best[i:k 1][::-1] improved True return best这是我压箱底的 2-opt 简版几十行不到几百个点的路径问题通常能比最近邻初始解改善 15%~25%。真正上生产的话我会把它嵌进 ALNS 框架里外层做破坏修复内层用 2-opt 精修。6. 上线之后才开始的那些坑模型跑通只是万里长征第一步真正磨人的是上线之后。这几件事我几乎每个项目都会遇到列出来给你提个醒。6.1 数据质量决定算法上限算法再好喂进去的数据有错出来的方案就是废的。我遇到过的典型问题包括距离矩阵用的是直线距离但实际要绕路、客户时间窗从 Excel 导入时被格式化成了整数、某些订单的载重要求和体积要求互相矛盾、还有最经典的“同一个客户在系统里有两个地址”。上线前一定要做数据体检空值检查、量纲检查、约束可行性预检比如总需求是否超过总运力。约束可行性预检特别重要。如果业务数据本身就让问题无解求解器只会返回 INFEASIBLE但不会告诉你哪条约束冲突。这时候需要把模型的约束一条条关掉重跑用二分法定位冲突源。我现在的习惯是先把所有硬约束都改成软约束加惩罚跑出解来之后再看哪些惩罚项被触发这样既避免了无解又能反推数据问题。6.2 时间预算要和业务节奏对齐我做过一个配送排程项目第一版模型在测试集上跑得挺好平均 40 秒出结果业务方看了没意见。上线之后才发现调度员的实际操作节奏是“边看边改”——改一个订单就要重算一次40 秒根本等不了。后来改成两段式先跑 3 秒出一个可用的粗解后台继续算 60 秒再替换成精解体验一下子顺了。这里的经验是永远给求解器设时间上限并且分档出解。OR-Tools 支持注册回调在求解过程中捕获每一个改进解我就用这个机制把“3 秒首个可行解、10 秒次优解、60 秒最终解”三级方案推给前端。用户看到进度条在动容忍度会高很多。6.3 解的稳定性和可解释性算法解出来的方案如果每次运行都和上次差很多调度员会直接不信任它。我遇到过一次两个方案的 makespan 只差 0.3%但任务分配完全不同调度员看了一脸懵“上次挺好的这次怎么全变了”后来我在目标函数里加了一个稳定性惩罚项对偏离上一版方案的操作加一个很小的成本方案就稳定多了。可解释性同样重要。求解器只会给你一堆变量取值业务人员看不懂。我一般会做一个“变更报告”相比人工方案哪些订单换了车、为什么换比如“合并后节省 12 公里”。有了归因人才愿意接受算法建议。纯黑盒的方案哪怕真优化了落地的阻力也会大很多。6.4 热启动与增量求解每次改动都从头算是最浪费的做法。我常用的两个优化一是热启动。把上一次的解作为初始解喂给求解器很多求解器包括 CP-SAT都支持通过AddHint给变量赋初始值。在有时间上限的情况下一个好的初始解能显著提升最终解的质量。二是增量求解。如果只是加了几个订单、改了一个时间窗不需要重建整个模型。CP-SAT 支持修改已有模型的部分约束后重新求解比从零建模省下大量预处理时间。我做过对比增量求解在“小改动”场景下通常能把响应时间压到原来的三分之一左右。最后分享个我自己的小习惯每次模型调优我都会用固定的一组测试实例跑一遍回归记录目标值、求解时间、gap 三个指标存成 CSV。调参这件事太容易陷入“改了这个坏了那个”的循环有回归数据打底至少知道自己是往前走了还是原地打转。这个习惯看着笨但真的省了我不少返工的时间。