1. 从一次求解失败说起为什么options不是可有可无的装饰很多人第一次用intlinprog求解整数线性规划都是照着文档抄一段代码把系数矩阵填进去然后直接跑。结果要么是求解时间长得离谱要么是提示未找到可行解要么是求解精度差得让人怀疑人生。我见过不少同学在这个阶段就开始怀疑自己的模型建错了反复检查约束条件折腾半天最后发现问题根本不在模型上而在于options这个参数压根没配置。intlinprog是 MATLAB 中用于求解混合整数线性规划MILP的核心函数它的标准调用形式里options是一个可选参数但可选绝不等于可以忽略。这个参数本质上是一个结构体里面装着求解器的各种行为开关用哪种分支定界策略、节点搜索的优先级怎么排、相对间隙容差设多大、是否显示迭代日志、最大求解时间是多少、整数可行性容差怎么定……这些设置直接决定了求解器在解空间里怎么走、走多快、什么时候停下来。打个比方intlinprog就像一辆性能很强的越野车模型是你的目的地而options就是方向盘、油门、刹车和四驱模式的集合。你不碰它车也能往前开但可能走的是最绕的路遇到泥坑也不知道切换模式最后要么到不了要么油耗惊人。而一旦你理解了每个选项的含义就能根据问题的规模、结构和精度要求把这辆车调到最合适的状态。这篇文章面向的是已经会用intlinprog基本调用、但在求解效率和结果质量上遇到瓶颈的读者。我会把options里那些真正影响求解行为的字段逐个拆开讲清楚它们背后的求解器逻辑给出不同场景下的推荐配置并分享一些文档里不会写的调参经验。全文基于 MATLAB 官方文档中intlinprog的options结构体字段展开结合我在实际项目中反复试出来的参数组合力求让你看完就能直接改自己的代码。2. options结构体的全貌与字段分类逻辑2.1 一个结构体两大来源intlinprog的options结构体并不是凭空造出来的它由两部分字段合并而成一部分来自通用的优化选项通过optimoptions创建另一部分来自整数规划求解器特有的设置。理解这个来源划分很重要因为有些字段是所有优化函数共用的有些则是intlinprog独有的。用optimoptions(intlinprog)不带任何参数调用MATLAB 会返回一个包含所有可设置字段的默认结构体。你可以直接查看它也可以逐项修改。下面这张表列出了最核心的字段及其默认值先建立一个全局印象字段名默认值作用类别Displayfinal输出控制MaxTimeInf终止条件MaxNodesInf终止条件RelativeGapTolerance1e-4终止条件AbsoluteGapTolerance0终止条件IntegerTolerance1e-5数值容差ConstraintTolerance1e-6数值容差ObjectiveCutoff-Inf剪枝策略BranchRulemaxpscost分支策略NodeSelectionbestbound节点选择LPPreprocessbasic预处理RootLPAlgorithmdual-simplex根节点求解Heuristicsbasic启发式CutGenerationbasic割平面CutMaxIterations10割平面IPPreprocessbasic预处理PlotFcn[]可视化这张表里的字段按功能可以分成四类终止控制类决定什么时候停、搜索策略类决定怎么搜、数值容差类决定什么算可行、什么算整数、输出与诊断类决定给你看什么。下面几节我会按这个分类逐一展开但不会机械地照搬文档而是重点讲每个字段在什么情况下会真正影响你的求解结果。2.2 为什么默认值不是万能的MATLAB 给这些字段选的默认值是在大量测试问题上折中出来的通用配置。通用意味着它在大多数问题上不会太差但也意味着它在你的特定问题上很可能不是最优。举个最直观的例子RelativeGapTolerance默认是1e-4意思是当当前找到的最好整数解的目标函数值与松弛问题的下界之间的相对差距小于万分之一时求解器就认为够好了停止搜索。对于一个小规模问题这个精度可能几秒钟就达到了但对于一个上百个变量、约束复杂的调度问题可能跑几个小时都达不到这个间隙而实际上你只需要一个误差在百分之一以内的可行解就够了。这时候如果不把RelativeGapTolerance放宽到1e-2就是在白白浪费时间。再比如Display默认是final只给你看最终结果。但在调试阶段你根本不知道求解器卡在哪一步、当前下界是多少、有没有找到可行解。把它改成iter你就能看到每次迭代的详细信息这对判断模型是否合理、参数是否合适至关重要。所以理解options的第一步就是放弃默认值够用的幻想根据问题特征主动配置。3. 终止条件类选项让求解器在该停的时候停下来3.1 RelativeGapTolerance与AbsoluteGapTolerance的配合这两个字段是控制求解精度的核心。RelativeGapTolerance定义的是相对间隙计算公式是相对间隙 |当前最好整数解目标值 - 全局下界| / max(1, |当前最好整数解目标值|)当这个值小于设定的容差时求解器停止。AbsoluteGapTolerance则是绝对间隙当最好整数解目标值与下界之差的绝对值小于它时停止。两个条件是或的关系满足任意一个就停。这里有个很容易踩的坑很多人只调RelativeGapTolerance忽略了AbsoluteGapTolerance默认是0。在某些目标函数值本身就很小的场景下比如目标值在 0.001 量级相对间隙的分母max(1, |目标值|)会取 1导致相对间隙被严重放大求解器可能过早停止。这时候把AbsoluteGapTolerance设成一个合理的绝对值比如1e-6反而能获得更精确的解。我的经验是目标函数值量级在 1 以上时主要调相对间隙目标函数值量级很小或接近零时必须同时设置绝对间隙。另外如果你只是需要一个工程上可用的次优解把相对间隙放宽到1e-2甚至5e-2求解时间往往能缩短一个数量级而解的质量下降非常有限。3.2 MaxTime与MaxNodes给求解过程上保险MaxTime设置的是求解器允许运行的最大秒数默认Inf意味着不限时。MaxNodes设置的是分支定界树允许探索的最大节点数默认也是Inf。这两个字段在实际项目中的价值极高。我做过一个含 200 多个 0-1 变量的排班问题模型本身没问题但求解器跑了一整夜都没收敛。后来设置了MaxTime 300五分钟内就返回了一个可行解虽然不保证最优但排班效果已经比人工排的好很多。对于实际业务来说一个五分钟内拿到的次优解远比一个跑十小时才出来的最优解有价值。注意MaxTime和MaxNodes触发终止时求解器返回的是当前找到的最好可行解并会在输出信息里标明终止原因。如果连一个可行解都没找到返回的x可能是空的或不可行的这时候需要检查模型约束是否过紧。一个实用的组合策略是先用MaxTime 60快速跑一次看看能不能找到可行解、间隙大概在什么量级如果能找到且间隙不大再放宽时间限制做精细求解。这种两阶段做法比一上来就设Inf要高效得多。3.3 ObjectiveCutoff主动剪掉不够好的分支ObjectiveCutoff默认是-Inf表示不启用。当你把它设为一个具体数值时求解器会忽略所有目标函数值比这个截止值更差的解。这个字段在两种场景下特别有用。第一种是你已经通过其他方法比如启发式算法或上一轮求解得到了一个目标值为Z的可行解现在想验证是否存在更好的解。把ObjectiveCutoff设为Z求解器就会把所有不可能优于Z的分支直接剪掉搜索空间大幅缩小。第二种是在滚动优化场景中你有一个可接受的目标阈值低于这个阈值的解没有实际意义设上截止值可以避免求解器在无望的分支上浪费时间。需要提醒的是ObjectiveCutoff设得太紧可能导致可行域被完全剪掉求解器返回无可行解。所以设置之前最好对目标函数的合理范围有个估计。4. 搜索策略类选项决定求解器在解空间里怎么走4.1 BranchRule分支变量怎么选分支定界算法的核心操作是当松弛解中某个整数变量取了小数就选一个变量把它分支成两个子问题。BranchRule决定的就是这个选哪个变量的规则。默认值maxpscost是最大伪代价策略它综合考虑变量的分数部分和伪代价即变量每变化一个单位对目标函数的影响估计。除此之外还有mostfractional选分数部分最接近 0.5 的变量、first按变量顺序选第一个分数变量、strongbranching对候选变量做强分支测试选效果最好的。strongbranching通常能显著减少节点数但每个节点的计算开销大得多。对于小规模问题变量数几十个强分支往往划算对于大规模问题maxpscost或mostfractional更实用。我实测过一个 80 变量的背包问题strongbranching比默认策略少探索了约 40% 的节点但总时间只快了 15%因为单节点开销上去了。4.2 NodeSelection先探索哪个节点分支定界树会积累大量待探索的节点NodeSelection决定下一个探索哪个。默认bestbound选择下界最好的节点这有利于快速提升全局下界、证明最优性。另一个选项bestestimate选择估计目标值最好的节点更倾向于快速找到好的可行解。这两个策略的取舍很明确如果你关心的是尽快拿到一个好解用bestestimate如果你关心的是证明最优性或缩小间隙用bestbound。在限时求解的场景下我通常先用bestestimate快速找到一个可行解然后如果时间允许再切换到bestbound做精细搜索。4.3 Heuristics要不要花力气找可行解Heuristics控制求解器是否运行启发式算法来寻找整数可行解默认basic表示运行基本的启发式。设为none则完全关闭设为advanced会运行更耗时的启发式。启发式的作用是在分支定界的早期就找到一个可行解从而为剪枝提供依据。对于约束较紧、可行解难找的问题advanced往往值得一试。但如果你的问题可行解很容易找比如约束很松启发式就是浪费时间设none反而更快。4.4 CutGeneration与CutMaxIterations割平面怎么加割平面是提升下界、缩小搜索空间的重要手段。CutGeneration默认basic可以设为none不加割、intermediate中等强度、advanced高强度。CutMaxIterations控制每轮加割的最大迭代次数默认 10。加割能显著减少节点数但每轮加割本身也有计算成本。对于结构复杂的问题advanced配合较大的CutMaxIterations通常能带来明显收益。我处理过一个含大量逻辑约束的选址问题把CutGeneration从basic调到advanced后求解时间从 800 多秒降到了 200 秒左右效果非常明显。5. 数值容差与预处理那些容易被忽视但影响巨大的细节5.1 IntegerTolerance什么算整数IntegerTolerance默认1e-5意思是当一个变量的值与其最近整数的偏差小于这个容差时就认为它满足整数约束。这个值设得太小求解器会因为浮点误差把本应可行的解判为不可行导致找不到解或反复分支设得太大又可能把明显不是整数的解当成整数得到错误的最优解。对于变量取值范围很大的问题比如变量可以取到几千浮点误差的绝对量会更大这时候适当放宽IntegerTolerance到1e-4甚至1e-3是合理的。5.2 ConstraintTolerance约束满足到什么程度算满足ConstraintTolerance默认1e-6控制线性约束的可行性判定。和IntegerTolerance类似这个值也需要根据问题的数值尺度来调整。如果约束矩阵中的系数跨度很大有的系数是 0.001有的是 10000默认容差可能导致数值上的误判。我的建议是在求解之前先对模型做尺度分析。如果系数跨度超过 6 个数量级考虑对变量和约束做归一化或者适当放宽ConstraintTolerance。归一化虽然麻烦但往往比调容差更可靠。5.3 LPPreprocess与IPPreprocess预处理到底做了什么LPPreprocess默认basic控制线性规划预处理包括移除冗余约束、收紧变量边界、检测不可行性等。IPPreprocess默认basic控制整数规划层面的预处理比如系数强化、探测固定变量等。预处理能大幅简化问题但偶尔也会因为数值问题引入误差。如果发现求解结果异常可以尝试把这两个字段设为none排除预处理的影响。不过大多数情况下保持默认的basic是最稳妥的选择。5.4 RootLPAlgorithm根节点用什么算法RootLPAlgorithm默认dual-simplex也可以设为interior-point。对偶单纯形在大多数 MILP 问题上表现稳定而内点法在问题规模很大、约束很稠密时可能更快。这个字段一般不需要动除非你明确知道自己的问题类型更适合内点法。6. 输出与诊断让求解过程可见、可调、可复现6.1 Display的四个档位Display有四个可选值off不输出、final只输出最终结果、iter每次迭代输出、iter-detailed详细迭代信息。调试阶段强烈建议用iter。你会看到每次迭代的节点数、当前最好整数解目标值、全局下界、相对间隙等信息。这些信息能帮你判断求解器是在稳步推进还是卡住了间隙是在缩小还是停滞如果跑了很久间隙都不动说明模型或参数需要调整。6.2 PlotFcn把求解过程画出来PlotFcn可以接受一个函数句柄把求解过程中的关键指标实时画出来。MATLAB 提供了一些内置的绘图函数比如显示分支定界树、显示间隙变化曲线等。对于需要向团队汇报或分析求解行为的场景这个功能非常直观。6.3 输出信息的解读求解结束后intlinprog会返回一个output结构体里面包含output.absolutegap、output.relativegap、output.numnodes、output.message等字段。这些字段是判断求解质量的关键依据。比如output.relativegap告诉你最终解离理论最优有多远output.numnodes告诉你探索了多少节点。养成每次求解后检查这些字段的习惯能帮你快速定位问题。7. 不同场景下的参数组合实战7.1 小规模精确求解变量数在 50 以内、需要精确最优解的场景推荐配置options optimoptions(intlinprog, ... Display, iter, ... RelativeGapTolerance, 1e-6, ... AbsoluteGapTolerance, 1e-8, ... BranchRule, strongbranching, ... CutGeneration, advanced, ... MaxTime, 600);小规模问题不怕单节点开销大强分支和高强度割平面能快速收敛到最优。7.2 大规模限时求次优解变量数上百、需要在有限时间内拿到可用解的场景options optimoptions(intlinprog, ... Display, iter, ... RelativeGapTolerance, 1e-2, ... MaxTime, 300, ... NodeSelection, bestestimate, ... Heuristics, advanced, ... CutGeneration, basic);放宽间隙、限时、优先找可行解是这类场景的核心思路。7.3 数值不稳定问题的排查配置当求解结果异常、怀疑数值问题时options optimoptions(intlinprog, ... Display, iter-detailed, ... IntegerTolerance, 1e-4, ... ConstraintTolerance, 1e-5, ... LPPreprocess, none, ... IPPreprocess, none);关闭预处理、放宽容差先确认问题是否出在数值层面。8. 几个文档里不会写的调参心得第一个心得先看间隙曲线再调参数。把Display设为iter跑一次观察相对间隙随时间的变化。如果间隙在前 10% 的时间里就降到了 1% 以内后面一直在缓慢下降说明求解器已经找到了好解只是在证明最优性上花时间这时候放宽间隙容差就能省下大量时间。如果间隙一直居高不下说明模型本身可能有问题调参数救不了。第二个心得MaxTime 不要设成整数。设成 300 秒和 299 秒没有本质区别但设成 300 秒时如果求解器在第 299 秒找到了一个好解它可能来不及完成当前节点的处理就超时了。我习惯设成 297 或 303 这种非整数虽然听起来有点玄学但实测中确实偶尔能避免在关键节点被硬切断。第三个心得善用 ObjectiveCutoff 做滚动优化。在需要反复求解相似问题的场景比如每天排班可以把上一次求解的目标值作为这一次的ObjectiveCutoff这样求解器会自动跳过所有不可能更优的分支随着时间推移求解速度会越来越快。第四个心得options 是可以增量修改的。不需要每次都用optimoptions从头创建可以先创建一次然后在不同求解中修改个别字段options optimoptions(intlinprog, Display, off); % 第一次求解 options.MaxTime 60; [x1, fval1] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub, options); % 第二次求解只改时间限制 options.MaxTime 300; options.RelativeGapTolerance 1e-3; [x2, fval2] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub, options);这种写法在参数扫描和对比实验中特别方便。第五个心得记录每次求解的 output 结构体。把output.relativegap、output.numnodes、output.message存下来时间长了就能建立起什么样的参数组合对应什么样的求解表现的直觉。这比任何文档都管用。9. 常见报错与 options 的关联排查9.1 No feasible solution found这个报错最常见的原因不是模型真的无解而是ConstraintTolerance或IntegerTolerance设得太紧导致数值上可行的解被判为不可行。排查方法先把两个容差都放宽一个数量级如果还是无解再检查约束是否真的矛盾。9.2 Exiting: time limit exceeded这是MaxTime触发的正常终止不是错误。但如果你发现每次都在时间限制处停止且间隙很大说明时间给少了或者模型太难。可以尝试放宽间隙容差、改用bestestimate节点选择、开启advanced启发式。9.3 Exiting: objective function value below cutoff这是ObjectiveCutoff触发的终止说明求解器找到了比截止值更好的解。如果你不希望它提前停止把ObjectiveCutoff设回-Inf即可。9.4 求解结果与预期不符如果求解器返回了一个最优解但你手动验证发现它不满足某些约束大概率是ConstraintTolerance太宽把违反约束的解当成了可行解。把容差收紧到1e-8再试一次如果解变了说明原解的约束违反量在容差范围内需要根据实际精度要求决定是否接受。10. 把 options 当成模型的一部分来对待我刚开始用intlinprog的时候总觉得options是附属品模型才是主角。后来踩的坑多了才明白对于整数规划来说模型和求解参数是一体的。同一个模型参数配得好几秒钟出结果配得不好跑一晚上还在转。这不是求解器的问题是我没把options当回事。现在我的习惯是每建一个新模型先用默认参数跑一次看output里的间隙和节点数然后根据问题规模设MaxTime根据精度要求设间隙容差根据求解表现决定要不要开强分支或高级割平面。这套流程走下来大多数问题都能在可接受的时间内拿到可用的解。如果你也在用intlinprog但还没认真配过options建议从Display改成iter开始先看清楚求解器在干什么再决定怎么调。这一步迈出去你对整数规划求解的理解会上一个台阶。
