Approximating the stability region for binary mixed-integer programs

The stability region of a solution is the polyhedral set of objective coefficients for which the solution is optimal. It provides valuable information for sensitivity analysis and re-optimization. An exact description of it may require an exponential number of inequalities. We develop polyhedral inner and outer approximations of linear size.