We consider optimization problems with some binary variables, where the objective function is linear in these variables. The stability region of a given solution of such a problem is the polyhedral set of objective coefficients for which the solution is optimal. A priori knowledge of this set provides valuable information for sensitivity analysis and re-optimization when there is objective coefficient uncertainty. An exact description of the stability region typically requires an exponential number of inequalities. We develop useful polyhedral inner and outer approximations of the stability region using only a linear number of inequalities. Furthermore, when a new objective function is not in the stability region, we produce a list of good solutions that can be used as a quick heuristic or as a warm start for future solves.
Article
View Approximating the Stability Region for Binary Mixed-Integer Programs