For registration information
please contact:

Janet Delsey
905-525-9140, ext. 24910
delsey@mcmaster.ca

Robust Optimization: A Tractable Theory of Stochastic Optimization

Dimitris Bertsimas
Sloan School of Management, MIT

We propose an approach to address optimization under uncertainty
that

(a) unlike dynamic and stochastic programming does not suffer from the curse of dimensionality,

(b) allows explicit control of the tradeoff of robustness and optimality,
and

(c) inherits the computational complexity of the underlying deterministic problem.

Examples of concrete results include:

(a) the robust counterpart of a linear programming problem (LP) is still an LP and of a mixed integer programming problem (MIP) is still a MIP of comparable size.

(b) The robust counterpart of a polynomially solvable 0-1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable.

(c) Robust network flows can also be solved as a polynomial number of modified network flow problems.

(d) The robust counterpart of an NP-hard alpha-approximable 0-1 discrete optimization problem, remains alpha-approximable.

(e) Robust conic optimization problems retain their original structure. Specifically, robust second order cone problems (SOCPs) remain SCOPs and robust semidefinite optimization problems (SDPs) remain SDPs.

(f) When applied to classical supply chain optimization problems, the approach leads to tractable solutions that extend the applicability of known results and lead to deeper insights.

(Joint work with Melvyn Sim and Aurelie Thiele)