Holger Heitsch,
Werner Römisch
Preprint series:
Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976),
MSC 2000
- 90C15 Stochastic programming
Abstract
We consider convex stochastic programs with an (approximate) initial
probability distribution P having finite support supp P, i.e.,
finitely many scenarios. Such stochastic programs behave 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 which 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 is considerably
improved. 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.
Keywords:
Stochastic programming, probability metric, scenario reduction,
scenario tree, electrical load