Mixed-Integer Program Sensitivity Analysis via Branch-and-Bound Trees

Source: arxiv.org/abs/2611.04415

Anna Deza, Fabian Badilla, Santanu S. Dey

arXivarxiv/2611.04415Nov 3, 2026math.OCscore 0

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…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.04415
curl -X POST /api/v1/records/arxiv/2611.04415/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.04415/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'