Mixed-Integer Program Sensitivity Analysis via Branch-and-Bound Trees
Abstract
We study how to compute valid dual bounds for mixed-integer linear programs (MILPs) with finite variable bounds under data perturbations. In an offline-online setting, a nominal instance is solved once and its information is reused to evaluate perturbations. We develop a framework for linear programs under simultaneous perturbations to the objective coefficients, right-hand side, and constraint matrix. Our construction is based on a bounded Lagrangian dual evaluated at nominal optimal dual multipliers. We prove that its gap to the perturbed LP optimal value grows at most linearly with perturbation magnitude under suitable conditions. We extend this construction to MILPs by reusing the nominal branch-and-bound tree and node-level dual information, generalizing the sensitivity analysis framework of Schrage and Wolsey (1985) to all problem data. To strengthen the dual bounds, we adapt their subtree-selection dynamic program. The online computations support GPU acceleration and highly parallel evaluation of dual bounds, which can also certify optimal variable fixings and accelerate reoptimization. Experiments on generalized independent set, combinatorial auction, capacitated facility location, and unit commitment instances produce tight dual bounds at low computational cost. For single-parameter ``what-if'' perturbations, gaps are typically a small fraction of a percent, with GPU evaluation times below a millisecond per perturbation. Relative to the time Gurobi needs to obtain bounds of the same quality, GPU evaluation is approximately 2,000--240,000 times faster for single-parameter perturbations and 120--50,000 times faster for multi-parameter perturbations. Using exact perturbed optima as supplied primal cutoffs, variable fixing accelerates exact reoptimization by up to a factor of 10 for generalized independent set instances, with little or no improvement for unit commitment.
Related
- A branch-and-filter method for mixed-integer linear programming
- Global Optimization of Mixed-Integer Bound-Constrained Quadratic Fractional Problems
- First-Order Primal-Dual Repairs for Scalable Branch and Bound
- Exact computation of the network modularity with branch-and-bound
- Bipolar Fuzzy Minimum-Weight Satisfiability under Continuous t-Norms: A Clause-Witness Branch-and-Bound Framework
BibTeX
@misc{deza2026mixedinteger,
title = {{Mixed-Integer Program Sensitivity Analysis via Branch-and-Bound Trees}},
author = {Anna Deza and Fabian Badilla and Santanu S. Dey},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04415},
eprint = {2611.04415},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04415},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Mixed-Integer Program Sensitivity Analysis via Branch-and-Bound Trees
AU - Anna Deza
AU - Fabian Badilla
AU - Santanu S. Dey
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04415
UR - https://arxiv.org/abs/2611.04415
AB - We study how to compute valid dual bounds for mixed-integer linear programs (MILPs) with finite variable bounds under data perturbations. In an offline-online setting, a nominal instance is solved once and its information is reused to evaluate perturbations. We develop a framework for linear programs under simultaneous perturbations to the objective coefficients, right-hand side, and constraint matrix. Our construction is based on a bounded Lagrangian dual evaluated at nominal optimal dual multipliers. We prove that its gap to the perturbed LP optimal value grows at most linearly with perturbation magnitude under suitable conditions. We extend this construction to MILPs by reusing the nominal branch-and-bound tree and node-level dual information, generalizing the sensitivity analysis framework of Schrage and Wolsey (1985) to all problem data. To strengthen the dual bounds, we adapt their subtree-selection dynamic program. The online computations support GPU acceleration and highly parallel evaluation of dual bounds, which can also certify optimal variable fixings and accelerate reoptimization. Experiments on generalized independent set, combinatorial auction, capacitated facility location, and unit commitment instances produce tight dual bounds at low computational cost. For single-parameter ``what-if'' perturbations, gaps are typically a small fraction of a percent, with GPU evaluation times below a millisecond per perturbation. Relative to the time Gurobi needs to obtain bounds of the same quality, GPU evaluation is approximately 2,000--240,000 times faster for single-parameter perturbations and 120--50,000 times faster for multi-parameter perturbations. Using exact perturbed optima as supplied primal cutoffs, variable fixing accelerates exact reoptimization by up to a factor of 10 for generalized independent set instances, with little or no improvement for unit commitment.
ER -