*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
