How variable is mixed integer programming solver performance and can it be predicted?

One instance, 100 seeds, wildly different runs

The clearest entry point is a single MIPLIB 2017 problem, neos-2624317-amur, solved 100 times with SCIP under identical parameter settings and a four-hour limit. Only the random seed varied. Most runs finished in well under a minute, but 11 hit the four-hour limit. Total LP iterations ranged from 1.2×10^5 to 8.1×10^7, and explored branch-and-bound nodes from 2,837 to 3,794,640.

This is what the paper calls performance variability: mathematically equivalent versions of the same problem, under seemingly neutral perturbations, produce very different search trajectories. The authors note the phenomenon has been discussed for decades in satisfiability and constraint programming, and cite the MIPLIB instance 10teams as a widely cited MIP example, where CPLEX needed 0.41 seconds and 2,731 LP iterations on one system versus 41.39 seconds and 122,948 LP iterations on another.

The practical consequence is that a single run is a weak estimate of an instance's difficulty. That matters for benchmarking and for interpreting computational studies, because an apparent speedup between two algorithms could be sampling noise rather than a real effect.

Why a single variability number needed four components

Earlier MIP variability measures were mostly time-based. The MIPLIB 2010 study summarized time-to-optimality dispersion with a coefficient of variation, the sample standard deviation of solution times divided by their mean. That statistic is scale-free and easy to compute, but it ignores solution quality and work measures, and because it is defined on time-to-optimality, timeouts and unsolved runs need ad hoc handling.

The authors wanted a per-instance index that reflects dispersion in several performance indicators, is scale-free, handles timeouts naturally, is not dominated by a few extreme runs, and can be decomposed back into components. They build it from four per-run measures: normalized time, where runtime is capped at the time limit and divided by it so every value falls in (0,1] and time-limited runs equal 1; final relative gap, capped at 1; total LP iterations; and total processed branch-and-bound nodes.

For each component they compute a modified coefficient of variation. Instead of the classical standard deviation over mean, each run's squared deviation is weighted by 1/(1+z^2), where z is that run's standardized deviation. Extreme runs therefore contribute less, which keeps a handful of outliers from dominating the score. The four component dispersions are then combined into the Weighted Variability Score, or WVS.

The distinction matters for readers: WVS is not a runtime statistic. An instance can be stable in time but unstable in nodes or LP iterations, and the paper reports that component contributions differ across metrics.

Most instances are stable, a tail is not

The empirical study covers MIPLIB 2017, a collection of 1,065 instances from academic and industrial sources. Each instance was run 100 times under default parameters with only the internal random seed varied; for SCIP the authors also enabled random permutation of constraints and variables. Every run used a four-hour wall-clock limit and a common memory limit, on identical single-threaded Azure virtual machines. Instances with more than 10 incomplete runs were excluded, leaving 1,009 instances in the main corpus. Of these, 388 were also run with Gurobi under the same protocol, forming the cross-solver subset.

Across this corpus, WVS has a right-skewed distribution with a substantial upper tail. Many instances are essentially stable, but some exhibit large variability that the authors say is not explained by basic properties alone. The variability is also not a simple monotone function of instance scale or difficulty.

The study produced an incidental result worth noting: the repeated-run experiment proved optimality for the open instance neos-5045105-creuse in two SCIP runs. That is a concrete demonstration that extra seeds can change what a benchmark reports, not just how precisely it reports it.

Predicting instability from presolve and root signals

The second question is whether variability can be predicted before committing a large run budget. The predictor uses two feature groups. Static structural features are fixed for the instance: counts of variables, constraints and nonzeros; variable-type ratios; sparsity and aspect-ratio measures; summary statistics of objective coefficients and right-hand sides; and structural flags such as set-partitioning, set-covering, knapsack, indicator, precedence and cardinality constraints. Early-run dynamic features summarize inexpensive information from presolve and the root node: presolving time and rounds at different effort levels, model size remaining after presolve, root LP solving time and iterations, degeneracy and dual-activity proxies, fractional variables, branching candidates and symmetry indicators.

The final model is a CatBoost tree ensemble with a gated tail uplift. Three tree experts are fit: a base expert with a Huber loss over the full WVS range, a synthetic-tail expert trained with SMOTE-style oversampling of mid- and high-WVS instances, and a tail expert trained with a 0.90 quantile loss. Logistic gates, with thresholds set from out-of-fold training predictions, gradually activate the specialized experts as the base prediction moves into the upper range, and the specialized experts may only add nonnegative corrections capped at 0.08. Gates and coefficients were frozen before any test evaluation.

On the sealed test split, this model achieves a mean absolute error of about 0.058 and a Spearman rank correlation of about 0.65 with WVS. The authors report that a Huber-tree baseline already improves substantially over ridge regression, and that the tail-focused expert sharpens rank quality and reduces error on the most variable instances without degrading global fit. As a robustness check, training separate models per component and combining them with the fixed WVS weights gave test error and rank correlation close to the direct model.

Root degeneracy and repeated coefficients drive the tail

TreeSHAP attributions decompose each prediction into feature contributions. The authors highlight root degeneracy, matrix structure, coefficient ranges and presolve reductions as the main drivers of high WVS.

One pattern is monotone: the ratio of binding constraints with zero dual values to total constraints. High values tend to push the predicted WVS upward, which the authors connect to dual degeneracy in solver instability. Their explanation is that a degenerate root relaxation creates many nearly equivalent bases and flat directions, so small perturbations in pricing or pivoting can propagate into substantially different search trees.

The analysis also complicates size-based intuitions. Large presolved cores, measured by nonzeros remaining after presolve, and long root LP-solving times are not by themselves reliable indicators of instability once other structural features are taken into account. A high ratio of unique objective coefficients to total nonzeros tends to be associated with lower predicted variability, while repetitive coefficient patterns are associated with higher predicted variability, consistent with the hypothesis that repeated coefficients create more cost-based ties. The interaction term combining the degeneracy index with the ratio of bounded variables ranks highly, suggesting degeneracy is especially destabilizing inside a tightly constrained residual model.

These are the authors' interpretations of feature importance, not causal experiments. They identify structure exposed at the root node as systematic, but the evidence is predictive association.

Where the score changes benchmarking decisions

The paper's practical proposal is not to run 100 seeds for every instance. It is to report WVS alongside standard aggregates, or at least flag high-WVS cases, so that an apparent performance gain can be distinguished from sampling noise. The authors also suggest that a new branching rule, cut family or heuristic can be evaluated by how much variability it introduces or removes.

The predictor supports a triage mechanism. Because it uses only static descriptors and root-level signals, it can be evaluated after presolve and the first LP relaxation. Instances with high predicted WVS are natural targets for larger budgets, extra seeds or bet-and-run strategies, while low-WVS instances appear safe for single-seed evaluation. The neos-5045105-creuse case is the paper's illustration of the upside: multiple seeds can turn an open instance into a solved one.

The authors also argue that variability should become an explicit tuning objective, with parameter sets compared not only on speed and solved counts but on their impact on WVS for selected instance families.

The boundaries are stated in the paper. Each WVS value is an estimate from a finite sample of 100 runs, so small differences in scores or predictions should not be overinterpreted. The study covers SCIP on the full corpus and Gurobi on a 388-instance subset, and the authors list additional solvers and versions, deeper tree-level signals, task-specific weight choices and coupling the forecaster to variability-aware policies as next steps.

The tail, not the average, is the decision point

The paper's most useful reframing is that variability is a per-instance property with a heavy tail, not a uniform noise floor. Most MIPLIB 2017 instances are essentially stable, so a single run is informative for them. The instances that matter for benchmarking risk are the minority in the upper tail, where seed choice can move runtime, gap, LP iterations and node counts by orders of magnitude.

That split is what makes the predictor worth attention. A mean absolute error of 0.058 and rank correlation of 0.65 are not a precise forecast of how unstable a run will be, but they are enough to rank instances after presolve and the root LP, which is exactly the point at which a budget decision has to be made. The paper's priority is therefore to spend extra seeds where predicted WVS is high and to treat low-WVS instances with a lighter protocol, rather than to sample uniformly or to trust a single default-seed result.

Sources used in this answer