Optimization under Uncertainty

This chapter reviews the main ideas behind dynamic programming, stochastic programming, and robust optimization, and illustrates the techniques with examples. It provides taxonomy of methods for optimization when the input parameters are uncertain. Dynamic programming solves a large multistage optimization problem sequentially, starting at the last stage and proceeding backward, thus keeping track only of the optimal paths from any given time period onward. The stochastic programming can be used to address the presence of uncertain input data in three types of optimization problems: expected value for single-stage and multistage models; models involving risk measures; and chance-constrained models. A major problem with dynamic and stochastic programming formulations is that in practice it is often difficult to obtain detailed information about the probability distributions of the uncertainties in the model. Robust optimization formulations can be used also in multistage settings to replace dynamic programming or stochastic programming algorithms.