Optimal scenario generation and reduction in stochastic programming

Abstract

Scenarios are indispensable ingredients for the numerical solution of stochastic optimization problems. Earlier approaches for optimal scenario generation and reduction are based on stability arguments involving distances of probabilitymeasures. In this paper we review those ideas and suggest to make use of stability estimates based on distances containing minimal information, i.e., on data appearing in the optimization model only. For linear two-stage stochasticprograms we show that the optimal scenario generation problem can be reformulatedas best approximation problem for the expected recourse function and asgeneralized semi-infinite program, respectively. The latter model turns out to beconvex if either right-hand sides or costs are random. We also review the problemsof optimal scenario reduction for two-stage models and of optimal scenario generationfor chance constrained programs. Finally, we consider scenario generationand reduction for the classical newsvendor problem.