Split Cuts for Robust Optimization

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