Scenario tree reduction for multistage stochastic programs

Abstract

A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the $L_r$-distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. Analgorithm is presented for selecting and removing nodes of a scenario tree suchthat a prescribed error tolerance is met. Some numerical experience is reported.