zbMATH — the first resource for mathematics

Scenario reduction algorithms in stochastic programming. (English) Zbl 1094.90024
Summary: We consider convex stochastic programs with an (approximate) initial probability distribution \(P\) having finite support supp \(P\), i.e., finitely many scenarios. The behaviour of such stochastic programs is stable with respect to perturbations of \(P\) measured in terms of a Fortet-Mourier probability metric. The problem of optimal scenario reduction consists in determining a probability measure that is supported by a subset of supp \(P\) of prescribed cardinality and is closest to \(P\) in terms of such a probability metric. Two new versions of forward and backward type algorithms are presented for computing such optimally reduced probability measures approximately. Compared to earlier versions, the computational performance (accuracy, running time) of the new algorithms has been improved considerably. Numerical experience is reported for different instances of scenario trees with computable optimal lower bounds. The test examples also include a ternary scenario tree representing the weekly electrical load process in a power management model.

90C15 Stochastic programming
90B90 Case-oriented studies in operations research
Full Text: DOI