Robust optimization is a paradigm for finding solutions to an

optimization problem when the data of the problem is not fixed,

but belongs to a well-defined uncertainty set. In this scheme,

one typically aims for a solution that minimizes (or maximizes)

an objective function against all possible realizations of the

data. From a complexity point of view a desirable property of

robust optimization models is that if the nominal problem (the

one with fixed data) is solvable in polynomial time, then so is

the robust counterpart. Nemirovski et al. have introduced several

robust convex optimization models for which this property holds.

Recently Bertsimas and Sim gave an MIP model for robust discrete

optimization. They showed that when uncertainty is in the objective coefficients, if a nominal 0-1 problem is solvable in polynomial time, so is the robust counterpart. However, the given robust model has typically very weak LP bound, which makes it difficult to solve in general.

In this talk we will describe alternative models for robust 0-1

programming. In particular, we will give three models, all of

which have the strongest possible LP relaxation independent of

the nominal 0-1 problem. In addition, we will show that there

is an LP formulation for a robust 0-1 problem, polynomial in the

size of the LP formulation of the nominal 0-1 problem. We will

give extensions to robust mixed 0-1 programming and conclude

with preliminary computational experience.