混合整数规划求解器性能波动有多大，能否预测？

同一实例，100 个种子，结果天差地别

最直观的切入点是 MIPLIB 2017 中的一个问题 neos-2624317-amur：在相同参数设置和四小时时限下，用 SCIP 求解 100 次，只改变随机种子。多数运行远不到一分钟就结束，但有 11 次撞上四小时时限。总 LP 迭代次数从 1.2×10^5 到 8.1×10^7，探索的分支定界节点数从 2,837 到 3,794,640。

这就是论文所说的性能波动：同一个问题在数学上等价的版本，在看似中性的扰动下，会产生非常不同的搜索轨迹。作者指出，这一现象在可满足性和约束规划领域已讨论数十年，并引用 MIPLIB 实例 10teams 作为 MIP 中常被引用的例子：CPLEX 在一个系统上需要 0.41 秒和 2,731 次 LP 迭代，在另一个系统上则需要 41.39 秒和 122,948 次 LP 迭代。

实际后果是，单次运行只能很弱地估计一个实例的难度。这会影响基准测试和对计算研究的解读，因为两种算法之间看似明显的加速，可能只是采样噪声，而非真实效果。

单一波动指标为何需要四个分量

早期的 MIP 波动度量大多基于时间。MIPLIB 2010 研究用变异系数概括求解到最优的时间离散程度，即求解时间的样本标准差除以均值。这个统计量无量纲、易计算，但忽略了求解质量和工作量指标；而且它定义在求解到最优的时间上，超时和未求解的运行需要额外处理。

作者想要一个逐实例的指标，它要反映多个性能指标的离散程度、无量纲、能自然处理超时、不被少数极端运行主导，并且可以分解回各分量。他们用四个逐次运行的度量来构建：归一化时间，即运行时间以时限为上限再除以时限，使每个值落在 (0,1] 内，超时运行等于 1；最终相对间隙，上限为 1；总 LP 迭代次数；以及总处理的分支定界节点数。

对每个分量，他们计算一个修正变异系数。它不用经典的“标准差除以均值”，而是把每次运行的平方偏差乘以权重 1/(1+z^2)，其中 z 是该次运行的标准化偏差。极端运行的贡献因此被压低，少数离群值无法主导评分。四个分量的离散度随后合并为加权波动评分，即 WVS。

这一区分对读者很重要：WVS 不是运行时间统计量。一个实例可能在时间上稳定，却在节点数或 LP 迭代次数上不稳定；论文也报告说，各分量的贡献在不同指标之间并不相同。

多数实例稳定，尾部并不稳定

实证研究覆盖 MIPLIB 2017，这是一个包含 1,065 个学术和工业来源实例的集合。每个实例在默认参数下运行 100 次，只改变求解器内部随机种子；对 SCIP，作者还启用了约束和变量的随机置换。每次运行使用四小时实际时间限制和统一内存限制，运行在相同的单线程 Azure 虚拟机上。不完整运行超过 10 次的实例被排除，主语料库剩下 1,009 个实例。其中 388 个还按相同协议用 Gurobi 运行，构成跨求解器子集。

在这个语料库上，WVS 呈右偏分布，并带有相当长的上尾。许多实例基本稳定，但有些实例表现出很大的波动，作者称这种波动无法用基本属性解释。波动也不是实例规模或难度的简单单调函数。

研究还产生了一个值得注意的附带结果：重复运行实验在两次 SCIP 运行中为开放实例 neos-5045105-creuse 证明了最优性。这具体说明，增加种子不仅改变基准测试报告的精确程度，还可能改变它报告的内容。

用预求解和根节点信号预测不稳定

第二个问题是，能否在投入大量运行预算之前预测波动。预测器使用两组特征。静态结构特征对实例固定不变：变量、约束和非零元数量；变量类型比例；稀疏度和行列宽高比度量；目标系数与右端项的汇总统计；以及集合划分、集合覆盖、背包、指示、优先和基数约束等结构标记。早期运行动态特征概括预求解和根节点阶段代价较低的信息：预求解时间及不同努力水平下的轮数、预求解后剩余模型规模、根 LP 求解时间和迭代次数、退化与对偶活跃度代理指标、分数变量、分支候选和对称性指标。

最终模型是带门控尾部提升的 CatBoost 树集成。它拟合三个树专家：一个在整个 WVS 范围上用 Huber 损失训练的基础专家；一个用 SMOTE 式过采样中高 WVS 训练实例的合成尾部专家；以及一个用 0.90 分位数损失训练、聚焦上界的尾部专家。逻辑门控的阈值由折外训练预测确定，随着基础预测进入上界区间逐步激活专门专家；专门专家只能添加非负修正，且修正上限为 0.08。门控和系数在任何测试评估之前就已冻结。

在封存测试集上，该模型与 WVS 的平均绝对误差约为 0.058，Spearman 秩相关约为 0.65。作者报告，Huber 树基线已明显优于岭回归，而聚焦尾部的专家进一步提升了排序质量，并降低了波动最大实例上的误差，同时没有损害整体拟合。作为稳健性检查，按分量分别训练模型、再用 WVS 的固定权重组合，所得测试误差和秩相关与直接模型接近。

根节点退化与重复系数推动尾部

TreeSHAP 归因把每个预测分解为各特征的贡献。作者指出，根节点退化、矩阵结构、系数取值范围和预求解约简是高 WVS 的主要驱动因素。

其中一个模式是单调的：对偶值为零的紧约束占总约束的比例。该比例高时倾向于推高预测 WVS，作者将其与求解器不稳定中的对偶退化联系起来。他们的解释是，退化的根松弛会产生许多近乎等价的基和大量平坦方向，因此定价或主元选择中的微小扰动可能传播成显著不同的搜索树。

分析也打破了基于规模的直觉。以预求解后剩余非零元衡量的大预求解核心，以及较长的根 LP 求解时间，在考虑其他结构特征后，本身并不是可靠的不稳定指标。唯一目标系数占总非零元的比例高，往往与更低的预测波动相关；而重复的系数模式则与更高的预测波动相关，这与“重复系数制造更多基于成本的并列”的假设一致。把退化指数与有界变量比例相乘的交互项排名靠前，说明退化在紧约束的残余模型中尤其具有破坏性。

这些是作者对特征重要性的解释，不是因果实验。他们把根节点暴露出的结构认定为系统性因素，但证据是预测性关联。

评分在何处改变基准测试决策

论文的实际建议不是对每个实例都运行 100 个种子，而是把 WVS 与标准汇总指标一起报告，或至少标记高 WVS 案例，从而把表面上的性能提升与采样噪声区分开。作者还建议，可以用新分支规则、割平面族或启发式引入或消除了多少波动来评估它们。

预测器支持一种分诊机制。由于它只使用静态描述符和根节点信号，可以在预求解和第一次 LP 松弛之后进行评估。预测 WVS 高的实例，自然适合投入更大预算、更多种子或 bet-and-run 策略；而低 WVS 实例看起来可以安全地单种子评估。neos-5045105-creuse 案例是论文用来说明收益的例子：多个种子可以把一个开放实例变成已求解实例。

作者还主张，波动应成为明确的调参目标：比较参数集时，不仅看速度和求解数量，还要看它们对选定实例族 WVS 的影响。

论文也说明了边界。每个 WVS 值都是基于 100 次运行的有限样本估计，因此评分或预测上的小差异不应过度解读。研究覆盖完整语料库上的 SCIP，以及 388 个实例子集上的 Gurobi；作者把更多求解器和版本、更深的树级信号、任务特定的权重选择，以及把预测器与波动感知策略耦合，列为后续工作。

决策点在尾部，不在平均值

论文最有用的重新定位是：波动是逐实例属性，且带有重尾，而不是均匀的噪声底。多数 MIPLIB 2017 实例基本稳定，因此对它们来说单次运行是有信息量的。对基准测试风险真正重要的是上尾中的少数实例：在这些实例上，种子选择可以让运行时间、间隙、LP 迭代次数和节点数相差几个数量级。

正是这种划分让预测器值得关注。0.058 的平均绝对误差和 0.65 的秩相关，并不足以精确预测一次运行会有多不稳定，但足以在预求解和根 LP 之后对实例排序，而这正是必须做出预算决策的时刻。因此，论文的优先事项是：在预测 WVS 高的地方多花种子，对低 WVS 实例采用更轻的协议，而不是均匀采样或相信单次默认种子结果。

本文引用的文献