Strong Formulations of Robust Mixed 0-1 Programming

We describe strong mixed-integer programming formulations for robust mixed 0-1 programming with uncertainty in the objective coefficients. In particular, we focus on an objective uncertainty set described as a polytope with a budget constraint. We show that for a robust 0-1 problem, there is a tight linear programming formulation with size polynomial in the size of a tight linear programming formulation for the nominal 0-1 problem. Finally, we give extensions to robust mixed 0-1 programming and present computational experiments with the strong formulations.


Mathematical Programming 108, 235-250, 2006