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

The Weighted Variability Score (WVS) is introduced as a robust, multi-component metric designed to aggregate dispersion in normalized runtime, final optimality gap, LP iterations, and branch-and-bound nodes across repeated runs to quantify performance variability in mixed integer programming solvers. This research matters because it provides a tool for preemptive tuning and fairer evaluation of new algorithms by identifying which structural features drive solver instability.

How it works

The core contribution is the Weighted Variability Score (WVS), which is defined as a weighted sum of four component modified coefficients of variation (MCV) for normalized time, final gap, LP iterations, and branch-and-bound nodes. The MCV down-weights extreme standardized deviations using the formula MCVc = vutÍN j=1 wj(x j − μ) 2 / μ 2 ÍN j=1 wj, where wj = 1/(1 + zj 2) and zj = (xj − μ)/s if s > 0 (otherwise zj = 0). This construction ensures the score is scale-free, and timeout-robust.

The WVS is calculated for each instance–solver pair (i, s) using a weight vector w = (wT, wG, wI, wB) summing to one. The weights are chosen by searching over a discrete grid on the simplex Δ = [w ∈ R 4 ≥0: wT + wG + wI + wB = 1]. For each candidate weight vector, the score is defined as WVSi,s (w) = wT MCVT i,s + wG MCVG i,s + wI MCVI i,s + wB MCVB i,s. The weights used in the final calculation are fixed at (0.65, 0.05, 0.20, 0.10) for the SCIP–Gurobi overlap set.

Experimental Design and Features

The study utilized a broad subset of MIPLIB 2017 instances (1,065 instances), running each instance 100 times under identical parameter settings and varying only the solver’s internal random seed. The analysis involves extracting two groups of features: static structural features and early-run dynamic features. Static features include numbers of variables, constraints, and nonzeros; variable-type ratios (binary, general-integer, continuous); simple measures of sparsity and row/column aspect ratio. Dynamic features capture early presolving and root-node behavior under the standardized run protocol.

Empirical Characterization of Variability

The empirical distribution of 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. The analysis shows that WVS behaves as an additional axis, complementary to size and baseline difficulty, as correlations between WVSi and simple proxies like log10 of the number of constraints are moderate rather than near one.

Component-level behavior analysis showed that LP-iteration dispersion tracks time dispersion closely (correlation about 0.86), as expected, but remains useful on instances where many runs hit the time limit and time is censored. The decomposition of WVS into its four components shows that time contribution grows sharply and becomes dominant on average, while iterations and nodes continue to contribute in an instance-dependent way.

Predictive Modeling

A tree-based predictor with a gated tail uplift was built using static descriptors and root-level features. This model achieved a mean absolute error of 0.058 and Spearman rank correlation of 0.65 on a sealed test split. The final predictor uses three tree experts—a base expert, a synthetic-tail expert trained with SMOTE-style synthetic oversampling, and a tail expert trained with a 0.90 quantile loss—combined via logistic gates to add nonnegative corrections.

Discussion and Drivers

Feature-importance analysis using SHAP attributions highlights that root degeneracy, matrix structure, coefficient ranges, and presolve reductions as the main drivers of high WVS. The most consistent signals of instability are indicators of primal and dual inactivity: the ratio of binding constraints with zero dual values and the fraction of non-basic variables with zero reduced costs. The results suggest that variability is a systematic property of the numerical and combinatorial structure exposed at the root node.

Implications

The findings imply that variability can be reported alongside standard aggregates, allowing researchers to distinguish genuinely stable instances from those whose outcomes depend strongly on the random seed. The early-stage predictor suggests a simple triage mechanism where high predicted WVS instances are natural targets for larger budgets or bet-and-run strategies. Furthermore, the drivers point toward solver development, indicating that variability should be treated as an explicit tuning objective. The final predictor achieves a mean absolute error of about 0.058 and a Spearman rank correlation of about 0.65 with WVS.

The gist

WVS reveals a strongly rightskewed distribution with a substantial upper tail: many instances are essentially stable, but some exhibit large run-to-run variability that is not a simple monotone function of instance scale or difficulty.

1. Bold header: Incorporate Weighted Variability Score (WVS) into instance selection criteria. The WVS distinguishes genuinely stable instances from those whose outcomes depend strongly on the random seed, allowing researchers to report on performance robustness rather than just single-run metrics.

2. Bold header: Implement a tree-based predictor for preemptive tuning. This model, trained using static descriptors and root-level features, can be used as a simple triage mechanism to determine if an instance requires a larger budget, extra seeds, or bet-and-run strategies.

3. Bold header: Develop solver development targets based on feature importance. The analysis shows that variability is driven by factors like root degeneracy, matrix structure, coefficient ranges, and presolve reductions, indicating that parameter sets can be compared based on their impact on these specific instability drivers.