The goal of this work is to propose a tractable theory for optimization under uncertainty. The first motivation for robust optimization is data uncertainty for structured mathematical programming problems. Under this perspective, we investigate different choices of uncertainty sets to model data uncertainty and characterize the structure of the resulting robust counterparts. We particularly focus on uncertainty sets for which the robust problem inherits the computational complexity of the underlying deterministic problem. Examples of concrete results in this direction 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. The second motivation of robust optimization is to model stochastic and dynamic optimization problems using uncertainty sets as opposed to probability distributions. Unlike dynamic and stochastic programming this robust approach does not suffer from the curse of dimensionality. As a test case, we apply this perspective to classical supply chain optimization problems under uncertainty, and show (a) the proposed approach is computationally tractable for high dimensions and in many cases leads to stronger solutions, (b) the optimal robust policies have the same structure as optimal policies obtained via dynamic programming; moreover, the robust approach is capable of characterizing the structure of the optimal policy even in cases where the structure of the optimal policy obtained via dynamic programming is unknown. | ||