PaperlayerView exact revision on arXiv

Source-linked AI summary

When Solvers Get Moody: Quantifying and Predicting Performance Variability in Mixed Integer Programming

Mourchid Adegbindin, Brenda Dietrich, Jamol Pender, Andrea Lodi

arXiv:2610.12876v1math.OCcs.LG

TL;DR

Runtime alone does not capture variability in solution quality and solver effort, motivating a measure that combines these dimensions and a way to predict variability from early-run information. The paper introduces WVS and a tree-based predictor; WVS is right-skewed, and the predictor achieves about 0.058 mean absolute error and 0.65 Spearman correlation on a sealed test split.

  • Problem

    Runtime-only descriptions miss variation in final gaps and solver effort, motivating a holistic measure and prediction from early-run information.

    Source: §1.1 · p. 3, §6 · p. 13

  • Method

    WVS combines dispersion in normalized runtime, final gap, LP iterations, and branch-and-bound nodes; a tree-based predictor uses static descriptors and early-run features.

    Source: §3.1 · p. 5, §7 · p. 16

  • Results

    WVS is right-skewed, and its predictor achieves about 0.058 mean absolute error and 0.65 Spearman correlation on the sealed test split.

    Source: §7 · p. 16

  • Takeaways & Limitations

    Reporting WVS or flagging high-WVS instances can clarify whether apparent performance gains are robust rather than sampling noise.

    Source: §6 · p. 15

    Each WVS value estimates underlying variability from a finite sample, so small score or prediction differences should not be overinterpreted.

    Source: §6 · pp. 15–16

Abstract

from arXiv · show

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.

1. Introduction

Repeated runs show that neutral perturbations can produce sharply different solver outcomes, while existing work leaves open how to measure and predict variability for individual instances. The paper introduces WVS, characterizes variability across MIPLIB 2017, and develops a predictor using static and early-run information.

1. Introduction

  • With only the random seed changed, 11 of 100 runs of neos-2624317-amur hit the four-hour limit, while LP iterations ranged from 1.2 × 10^5 to 8.1 × 10^7.The runs also explored 2,837 to 3,794,640 branch-and-bound nodes.Source: §1 · p. 1

1.1. Relevant Literature

  • Prior studies document large run-to-run differences and describe ways to exploit variability, but solver configuration and prediction work typically target mean runtime rather than variability itself.Trajectory-based measures characterize progress within a run, not dispersion across runs on a fixed instance.Source: §1.1 · pp. 2–3
  • The paper asks how to measure solver variability robustly and whether it can be predicted from readily available information, especially root-node features.The motivation is that sampling or stabilization schemes applied where variability does not matter may be counterproductive.Source: §1.1 · p. 3

1.2. Summary of contributions

  • The contributions are WVS, repeated-run characterization of MIPLIB 2017, empirical analysis of solver effects, and a tree-based predictor interpreted with SHAP attributions.The protocol uses SCIP on most instances and Gurobi on a subset.Source: §1.2 · p. 3

2. Experimental Design

The study measures run-to-run variability on a filtered MIPLIB 2017 corpus using repeated seeded solver runs under controlled limits. It also collects static model descriptors and inexpensive presolve and root-node features for analysis and prediction.

2.1. Benchmark Instances, solvers, and run protocol

  • Each instance was run 100 times under default parameters, varying the solver seed; SCIP also permuted constraints and variables, with a four-hour wall-clock limit and common memory limit.Runs with more than 10 incomplete outcomes were excluded from the corpus.Source: §2.1 · pp. 3–4
  • After filtering, 1,009 instances remain in the main corpus; 388 were also run with Gurobi under the same protocol and form the subset used in cross-solver analyses.Source: §2.1 · p. 4
  • Runs used single-threaded SCIP 9.2.1 and, on the common subset, Gurobi 12.0.2 in uniform Azure virtual-machine conditions.The authors note that cloud infrastructure cannot eliminate all exogenous timing noise.Source: §2.1 · p. 4

2.2. Feature Extraction

  • Features combine static model structure and coefficients with presolve and root-node measurements, including effort, residual model size, degeneracy proxies, branching candidates, and symmetry indicators.Seed-varying dynamic quantities are aggregated across the 100 runs, for example by their mean or median.Source: §2.2 · p. 4

3. Defining and Measuring Solver Variability

The section motivates a per-instance measure of solver instability that captures several performance dimensions while remaining scale-free, timeout-robust, and interpretable. It constructs component-level dispersion measures and combines them into the Weighted Variability Score (WVS), with weights and a consensus rule for solver overlap.

3.1. Motivation

  • The score is motivated by the limits of time-only measures, which omit solution quality and work and require ad hoc handling of timeouts or unsolved runs.The desired per-instance index should also avoid being dominated by a few extreme runs and remain straightforward to interpret.Source: §3.1 · p. 5

3.2. Components and per-component dispersion

  • For each performance component, the modified coefficient of variation down-weights extreme standardized deviations, limiting the influence of a few outlying runs.The ordinary coefficient of variation can react strongly to extreme runs and become arbitrarily large when the mean is small.Source: §3.2 · p. 6

3.3. The Weighted Variability Score (WVS)

  • Time and final gap represent user-observed outcomes, while iterations and nodes proxy search effort; the representative weights are 0.65, 0.05, 0.20, and 0.10, respectively.Weights are selected on the SCIP–Gurobi overlap set; solver-overlap instances with disagreement above the tolerance are marked discordant and excluded from supervised learning, but retained for descriptive analysis.Source: §3.3 · pp. 6–7
  • WVS combines dispersion in normalized runtime, final gap, LP iterations, and branch-and-bound nodes into a scale-free, timeout-robust score that can be decomposed into four components.The authors describe it as stable under a few extreme runs and useful as a variability “condition number” for an instance–solver pair.Source: §3.3 · pp. 6–7

4. Empirical Characterization of Variability

Across the MIPLIB corpus, variability is right-skewed and not reducible to instance size or baseline runtime. Its component mix and cross-solver alignment vary, while current WVS retains a substantial association with the historical runtime-based score.

4.1. Overall Variability

  • Many instances have modest WVS, but a minority occupy a distinct high-variability regime across the size and runtime ranges.Correlations with size and mean normalized runtime are moderate; two SCIP runs also proved optimality for the then-open instance neos-5045105-creuse.Source: §4.1 · pp. 7–8
  • Exactly two of 100 SCIP runs proved optimality for neos-5045105-creuse within four hours, with runtimes of 122.77 and 10,424.45 seconds.The runs also differed substantially in LP iterations and branch-and-bound nodes.Source: §4.1 · p. 8

4.2. Component-Level Behavior

  • Time and LP-iteration dispersion correlate about 0.86, while gap and node dispersions are more modestly related, so no single component explains the others.At the high-WVS end, time contribution grows sharply and becomes dominant on average; iterations and nodes contribute variably, and gap contribution is generally smaller.Source: §4.2 · p. 8, §4.3 · p. 9

4.3. Historical Consistency with MIPLIB 2010

  • ρ=0.675 links legacy MIPLIB 2010 VS and current WVS on 38 common instances, rising to 0.740 when three 10-hour-affected values are excluded.The current runtime coefficient of variation is slightly more correlated with legacy VS: ρ=0.680 overall and ρ=0.767 excluding those values.Source: §4.3 · p. 8, Figure 4 · p. 10

4.4. Cross-Solver Alignment and Discordant Instances

  • On 388 shared instances, SCIP and Gurobi WVS rankings have a moderate positive association (Spearman ρ=0.403), with most instances low-variability for both solvers.A smaller nontrivial group is high-variability for both, while discordant cases are high for only one solver.Source: §4.3 · p. 9, Figure 3 · p. 9, §4.4 · p. 10

5. Predictive Modeling of Variability

This section predicts instance-level WVS from static descriptors and early solver features. A gated tail-uplift model performs on a sealed test split, while feature attributions highlight dual degeneracy and other structural signals.

5.1. Problem Setup and Evaluation Metrics

  • Static structure and SCIP early-presolve/root-node features are used; after consensus-label and modeling filters, 820 instances receive a frozen 90:10 split stratified by deciles of WVS*, with test data untouched until final evaluation.Skewed counts and effort measures are mapped with log(1 + x); several base quantities are converted to ratios or clipped, and feature screening uses training data only.Source: §5.1 · pp. 10–11

5.2. Models: Baselines and Final Predictor

  • The final CatBoost predictor blends a full-range Huber expert with synthetic-tail and 0.90-quantile experts, using gates and nonnegative corrections for the upper range.The model is compared with linear baselines and a Huber-loss boosted-tree baseline.Source: §5.2 · pp. 11–12

5.3. Training Protocol and Main Results

  • Tree hyperparameters are tuned by cross-validation to balance global MAE and top-decile MAE, with uplift coefficients fitted from out-of-fold training predictions.A sum-of-components predictor attains test MAE and rank correlation close to the direct WVS* head.Source: §5.3 · pp. 12–13
  • About 0.058 MAE and 0.65 Spearman rank correlation were achieved on the sealed test split; the tail expert reduced error on the most variable instances without degrading global fit.The Huber-tree baseline already improved substantially over ridge regression, and adding the tail-focused expert further sharpened rank quality.Source: §5.3 · p. 12, §5.2 · p. 12
  • TreeSHAP attributions show that high ratios of binding constraints with zero dual values tend to push predicted WVS* upward, consistent with dual degeneracy's role in solver instability.The analysis also reports feature-effect direction and spread; overlapping colors near zero indicate weaker or more interaction-dependent effects.Source: §5.3 · p. 13

6. Discussion

The discussion finds that runtime alone does not capture MIP solver variability: gap and solver-effort dispersion also matter, especially among high-WVS instances. Feature analyses associate variability with root degeneracy and the numerical and combinatorial structure remaining after presolve, while the authors note the finite-sample limits of their conclusions.

What Drives Variability

  • Runtime-only proxies correlate with WVS but do not fully explain its upper tail, where gap and solver-effort dispersion also contribute.The component-wise models find time easiest to predict, while gap and work components are noisier but not random; combining their predictions performs close to the direct WVS head.Source: §6 · p. 13
  • SHAP analysis identifies root degeneracy, coefficient patterns, and presolve-exposed combinatorial structure as drivers of WVS, rather than instance scale alone.Primal and dual inactivity indicators are consistent signals; the text links degenerate root relaxations to flat directions where small pricing or pivoting perturbations can lead to different search trees.Source: §6 · pp. 13, 15
  • Precedence constraints, mixed-binary variables, and active constraints after presolve rank highly, while presolved-core size and root LP time alone are not reliable instability indicators.The reported relationships are conditional on other structural features; variability is not a simple monotone function of problem size or computational effort.Source: §6 · p. 15
  • Higher unique objective-coefficient ratios tend to accompany lower predicted variability, while repetitive coefficients and degeneracy among bounded variables are associated with higher variability.The authors suggest repeated coefficients may create cost-based ties, and identify an interaction between degeneracy and the bounded-variable ratio.Source: §6 · p. 15

Implications, Limitations, and Next Steps

  • The authors propose reporting WVS alongside standard aggregates and using early-stage predictions to direct extra runs or solver budgets toward high-variability instances.They suggest treating variability as an explicit tuning objective when comparing parameter sets on selected instance families.Source: §6 · p. 15
  • Because the conclusions rest on a finite sample, each WVS value estimates underlying variability, and small score or prediction differences should not be overinterpreted.The authors identify additional solvers and versions, deeper tree-level signals, task-specific weights, and variability-aware policies as next steps.Source: §6 · pp. 15–16

7. Conclusion

The conclusion presents WVS as a scale-free, timeout-robust measure of solver instability and reports a right-skewed distribution across repeated MIPLIB 2017 runs. It also reports that early-run features predict WVS and that feature analyses point to root-level structure as a driver.

Conclusion

  • WVS aggregates down-weighted dispersion in normalized runtime, final gap, LP iterations, and branch-and-bound nodes into a scale-free index of solver instability.The index is described as timeout-robust.Source: §7 · p. 16
  • The MIPLIB 2017 repeated-run study finds a strongly right-skewed WVS distribution, with many stable instances and a minority showing large variability.The variability is not a simple monotone function of instance scale or difficulty.Source: §7 · p. 16
  • A tree-based predictor using static descriptors and early-run features attains about 0.058 mean absolute error and 0.65 Spearman correlation on a sealed test split.The predictor uses a gated tail uplift and identifies high-variability instances better than runtime-only proxies.Source: §7 · p. 16
  • Feature-importance analyses point to root degeneracy, dual inactivity, and numerical and combinatorial structure exposed at the root node as main drivers of variability.The authors present WVS and the predictor as a practical toolkit for reporting, understanding, and ultimately controlling variability in MIP.Source: §7 · p. 16

EC.1. Selected Feature Definitions

The appendix defines features used in interpreting feature-importance results, including measures of primal and dual inactivity, presolve structure, and root LP time.

EC.1. Selected Feature Definitions

  • frac_zero_rc is the ratio of non-basic variables with zero reduced cost to all non-basic variables, used as a proxy for primal degeneracy.Exact feature construction is provided in the reproducibility code.Source: EC.1. Selected Feature Definitions · p. 19
  • N_Bind_Cons_Zero_Dual_to_N_Cons_ratio divides binding constraints with zero dual value by the total number of constraints, serving as a proxy for dual inactivity.Exact feature construction is provided in the reproducibility code.Source: EC.1. Selected Feature Definitions · p. 19
  • Presol_Precedence counts precedence-type constraints remaining after presolve, while Presol_Nonzeroes counts nonzeros in the post-presolve constraint matrix.Exact feature construction is provided in the reproducibility code.Source: EC.1. Selected Feature Definitions · p. 19
  • LP_Solving_Time is an elapsed-time proxy from the first running-status statistics after presolving, aggregated across randomized runs at instance level.Exact feature construction is provided in the reproducibility code.Source: EC.1. Selected Feature Definitions · p. 19

EC.2. Historical Comparison with MIPLIB 2010

The historical comparison covers 38 instances shared by the MIPLIB 2010 variability study and the SCIP corpus, and reports legacy runtime-based variability scores alongside corresponding measures.

EC.2. Historical Comparison with MIPLIB 2010

EC.3. Additional Reproducibility Details

The reproducibility details trace the workflow from solver outputs through WVS calculation to reported results and specify the score’s component preprocessing and weights.

EC.3. Additional Reproducibility Details

Loading 2610.12876v1…