Problem-based optimal scenario generation and reduction in stochastic programming

Scenarios are indispensable ingredients for the numerical solution of stochastic programs. Earlier approaches to optimal scenario generation and reduction are based on stability arguments involving distances of probability measures. In this paper we review those ideas and suggest to make use of stability estimates based only on problem specific data. For linear two-stage stochastic programs we show that the problem-based approach to optimal scenario generation can be reformulated as best approximation problem for the expected recourse function which in turn can be rewritten as a generalized semi-infinite program. We show that the latter is convex if either right-hand sides or costs are random and can be transformed into a semi-infinite program in a number of cases. We also consider problem-based optimal scenario reduction for two-stage models and optimal scenario generation for chance constrained programs. Finally, we discuss problem-based scenario generation for the classical newsvendor problem.

Automated summary

This paper reviews previous approaches to optimal scenario generation and reduction and suggests using problem-specific data for stability estimates. For linear two-stage stochastic programs, the problem-based approach to optimal scenario generation can be reformulated as a best approximation problem and a generalized semi-infinite program. Convexity is shown for the latter when either right-hand sides or costs are random, and it can be transformed into a semi-infinite program in some cases. The paper also discusses problem-based scenario reduction for two-stage models and optimal scenario generation for chance constrained programs, as well as problem-based scenario generation for the classical newsvendor problem.