Hilfe Wegweiser Impressum Kontakt Einloggen





Split Cuts for Robust Optimization

Es sind keine MPG-Autoren in der Publikation vorhanden
Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Pfeuffer, F. (2010). Split Cuts for Robust Optimization. Talk presented at EngOpt 2010. Lisbon, Portugal. 2010-09-06 - 2010-09-09.

Real world mixed integer linear programming (MILP) models often contain numeric and hence uncertain data. We are interested in solutions to such problems which remain feasible under change of the problem data. This question is addressed by Robust MILP. We consider a notion of robustness where the coefficients of the constraint matrix are perturbed row-wise, where the perturbations are described by a polyhedrally encoded set. In this talk we are interested in the worst case strategy, i.e. solutions should be feasible under all possible perturbations. While MILP problems are routinely solved by Branch & Cut codes, little theory for our type of Robust MILP problems is available: usually one reformulates the robust problem as a regular MILP problem in a higher dimensional space. We present a generalization of the Lift & Project method, that directly handles robust problems, and show how the cut generation problems of our method and of a MILP reformulation of the robust problem are related. Computational results will be presented on robstified versions of MIPLIB and other MILP benchmark instances.