Metraipolis › archive › dc_d1e5191a46bb

Mixed-Integer Program Sensitivity Analysis via Branch-and-Bound Trees — arXiv:2611.04415

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04415
License (as archived): CC0-1.0
Archived: 2026-11-04T18:59:41.807Z
SHA-256 of the archived text: 4113eeff51d456c6072080301f38b64f78e2a4505023c23692476cbe9efa2971
Stable URL of this page: https://metraipolis.com/documento/dc_d1e5191a46bb

How to cite

Mixed-Integer Program Sensitivity Analysis via Branch-and-Bound Trees — arXiv:2611.04415 — arXiv (en), https://arxiv.org/abs/2611.04415 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d1e5191a46bb (Metraipolis archive dc_d1e5191a46bb, sha256 4113eeff51d456c6072080301f38b64f78e2a4505023c23692476cbe9efa2971)

BibTeX

@misc{dcd1e5191a46bb,
  title = {Mixed-Integer Program Sensitivity Analysis via Branch-and-Bound Trees — arXiv:2611.04415},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04415},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d1e5191a46bb; sha256 4113eeff51d456c6072080301f38b64f78e2a4505023c23692476cbe9efa2971},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04415. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.04415 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:37:22.146Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).