Scenario Reduction Algorithms in Stochastic Programming

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...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2003-02, Vol.24 (2-3), p.187-206
Main Authors: Heitsch, Holger, Romisch, Werner
Format: Article
Language:English
Subjects:
Algorithms
Probability
Probability distribution
Stochastic models
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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. [PUBLICATION ABSTRACT]
ISSN:0926-6003
1573-2894
DOI:10.1023/A:1021805924152