Strong formulations of robust mixed 0-1 programming

We introduce strong formulations for robust mixed 0-1 programming with uncertain objective coefficients. We focus on a polytopic uncertainty set described by a ``budget constraint'' for allowed uncertainty in the objective coefficients. We show that for a robust 0-1 problem, there is an alpha-tight linear programming formulation with size polynomial in the size of an alpha-tight linear programming formulation for the nominal 0-1 problem. We give extensions to robust mixed 0-1 programming and present computational experiments with the proposed formulations.