Mitigating Performance Variability in Mixed-Integer Programming Solvers via LP State Steering
Abstract
Modern mixed-integer programming (MIP) solvers repeatedly solve linear programming (LP) relaxations, but the LP state transferred from the simplex algorithm to the branch-and-bound tree is typically treated as an artifact of perturbation, presolve history, and numerical trajectory. This is harmless in pure linear programming, where alternative optimal bases certify the same bound. In MIP, however, those bases can expose distinct fractional structures, active rows, reduced costs, branching candidates, and reoptimization states. The inherited LP state is therefore an initial condition for the integer search. We exploit this initial condition to mitigate computational performance variability. The proposed framework generates alternative LP states on or near degenerate optimal faces, evaluates them within an auxiliary solver environment, and either selects a single state or executes a portfolio of candidate states in parallel. A handcrafted synthetic instance isolates the relationship between the initial LP state, the fractional profile, the branching trajectory, and the resulting node-count distribution: root-state steering reduces the weighted variability score~(WVS) by 67% over 1,000 paired seeds and produces no node-count regressions relative to default SCIP. On a separate 130-instance MIPLIB 2017 validation set with up to 50 paired seeds per instance, the top-five policy improves solve completion from 3,792 to 3,894 runs, reduces the shifted geometric mean of the recorded node count from 2,574.7 to 1,198.0, and lowers the median WVS by 9% on instances reliably solved by the baseline. These results demonstrate that the branch-and-bound phase inherits a specific LP state rather than merely an LP bound, and that the active management of this state systematically mitigates computational performance variability.
Related
- When Solvers Get Moody: Quantifying and Predicting Performance Variability in Mixed Integer Programming
- The exponent 1/4 in three complexity bounds: integer bases, continued fractions, and the (3/2)n steering word
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
- Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement
BibTeX
@misc{adegbindin2026mitigating,
title = {{Mitigating Performance Variability in Mixed-Integer Programming Solvers via LP State Steering}},
author = {Mourchid Adegbindin and Brenda Dietrich and Jamol Pender},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17268},
eprint = {2610.17268},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17268},
}
RIS
TY - UNPB
TI - Mitigating Performance Variability in Mixed-Integer Programming Solvers via LP State Steering
AU - Mourchid Adegbindin
AU - Brenda Dietrich
AU - Jamol Pender
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17268
UR - https://arxiv.org/abs/2610.17268
AB - Modern mixed-integer programming (MIP) solvers repeatedly solve linear programming (LP) relaxations, but the LP state transferred from the simplex algorithm to the branch-and-bound tree is typically treated as an artifact of perturbation, presolve history, and numerical trajectory. This is harmless in pure linear programming, where alternative optimal bases certify the same bound. In MIP, however, those bases can expose distinct fractional structures, active rows, reduced costs, branching candidates, and reoptimization states. The inherited LP state is therefore an initial condition for the integer search. We exploit this initial condition to mitigate computational performance variability. The proposed framework generates alternative LP states on or near degenerate optimal faces, evaluates them within an auxiliary solver environment, and either selects a single state or executes a portfolio of candidate states in parallel. A handcrafted synthetic instance isolates the relationship between the initial LP state, the fractional profile, the branching trajectory, and the resulting node-count distribution: root-state steering reduces the weighted variability score~(WVS) by 67% over 1,000 paired seeds and produces no node-count regressions relative to default SCIP. On a separate 130-instance MIPLIB 2017 validation set with up to 50 paired seeds per instance, the top-five policy improves solve completion from 3,792 to 3,894 runs, reduces the shifted geometric mean of the recorded node count from 2,574.7 to 1,198.0, and lowers the median WVS by 9% on instances reliably solved by the baseline. These results demonstrate that the branch-and-bound phase inherits a specific LP state rather than merely an LP bound, and that the active management of this state systematically mitigates computational performance variability.
ER -