A Tractable Theory of Stochastic Optimization
Sloan School of Management, MIT
We propose an approach
to address optimization under uncertainty
(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,
(c) inherits the computational
complexity of the underlying deterministic problem.
Examples of concrete
(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
(c) Robust network flows
can also be solved as a polynomial number of modified network flow
(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)