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.
Citation
Mathematical Programming 108, 235-250, 2006 http://www.ieor.berkeley.edu/~atamturk/pubs/