MIP solver performance variability mapped and predicted with new score
When Solvers Get Moody: Quantifying and Predicting Performance Variability in Mixed Integer Programming
Machine Learning
Summary
Solvers that tackle mixed-integer programming problems can run very differently even when nothing obvious changes. This makes it hard to compare solvers fairly. The authors created a new score called Weighted Variability Score (WVS) that measures how much solver results vary by looking at multiple factors. They found that some problem instances are stable while others have unpredictable runtimes, and that aspects of the problem’s structure help predict this variability. Their method helps decide when solvers need tuning and supports more trustworthy comparisons.
What this means in practice
- •For optimization engineers: Use early solver run data to predict variability and adjust solver settings proactively for more reliable optimization runs.
- •For operations research teams: Employ the variability score to identify problem instances with unstable solver behavior and guide resource planning and solver choice.
Authors
Mourchid Adegbindin, Brenda Dietrich, Jamol Pender, Andrea Lodi
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.