arXiv：cs.LG· Mourchid Adegbindin, Brenda Dietrich, Jamol Pender, Andrea Lodi·· 13 小时前
求解器也"闹情绪"：量化与预测混合整数规划中的性能波动
When Solvers Get Moody: Quantifying and Predicting Performance Variability in Mixed Integer Programming
AI 导读
研究提出加权波动评分（WVS），在 MIPLIB 2017 大规模子集上对每个实例做 100 次随机运行（四小时上限），汇总归一化运行时间、最终最优性间隙、LP 迭代次数和分支定界节点数的离散程度，发现分布右偏且存在明显长尾。
正文
Abstract:Mixed-integer programming (MIP) solvers are widely used, yet their performance can vary substantially even under seemingly neutral perturbations. Such variability complicates benchmarking, and the interpretation of computational studies. We introduce the Weighted Variability Score (WVS), a robust multi-component metric that aggregates dispersion in normalized runtime, final optimality gap, LP iterations, and branch-and-bound nodes across repeated runs. On a large subset of MIPLIB 2017 instances, each solved in 100 randomized runs under a four-hour limit, WVS reveals a right-skewed distribution with a substantial upper tail: many instances are essentially stable, but some exhibit large variability that is not explained by basic properties alone. Notably, this experiment proved optimality for the open instance 'neos-5045105-creuse' in two SCIP runs. Using static descriptors and root-level features, a tree-based predictor with a gated tail uplift achieves a mean absolute error of 0.058 and Spearman rank correlation of 0.65 on a sealed test split. Feature-importance analysis highlights root degeneracy, matrix structure, coefficient ranges, and presolve reductions as the main drivers of high WVS. Because variability is systematic and partially predictable from inexpensive early-run features, our findings offer a practical tool for preemptive tuning and lay a foundation for fairer evaluation of new algorithms.
| Comments: | 21 pages, including a 3-page electronic companion. An earlier conference version appeared in the IOS 2026 proceedings. this https URL |
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.12876 [math.OC] |
| (or arXiv:2610.12876v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.12876 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Mourchid Adegbindin [view email]
[v1]
Fri, 9 Oct 2026 02:09:26 UTC (1,868 KB)
来源：arXiv：cs.LG · arxiv.org