Optimization Online


Approximating the Stability Region for Binary Mixed-Integer Programs

F. Kilinc-Karzan(fkilinc***at***gatech.edu)
A. Toriello(atoriello***at***gatech.edu)
S. Ahmed(sahmed***at***isye.gatech.edu)
G. Nemhauser(gnemhaus***at***isye.gatech.edu)
M. Savelsbergh(mwps***at***isye.gatech.edu)

Abstract: 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.

Keywords: Real-time optimization, stability analysis, binary integer programming

Category 1: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 11/13/2007
Entry Accepted: 11/13/2007
Entry Last Modified: 11/13/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society