Strong Formulations of Robust Mixed 0-1 Programming

Event Details
  • Date/Time:
    • Wednesday October 15, 2003
      4:00 pm - 11:59 pm
  • Location: Main Building 228
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher

Summary Sentence: Strong Formulations of Robust Mixed 0-1 Programming

Full Summary: Strong Formulations of Robust Mixed 0-1 Programming

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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 8, 2010 - 7:42am
  • Last Updated: Oct 7, 2016 - 9:52pm