Robust Optimization: A Tractable Theory of Stochastic Optimization (Research Seminar, March 22, 2004) Dimitris Bertsimas MIT Abstract 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