Scenario reduction for stochastic programming models

GAMS Software GmbH Humboldt-Universitšt zu Berlin
Project director: Prof. Dr. W. Römisch, Humboldt-Universität Berlin, Tel: 030-2093 2561/ Secr. 2353, 
Collaborators:  Dr. Nicole Gröwe-Kuska, Humboldt-Universität Berlin, Tel: 030-2093 2262,  
Dipl.-Math. Holger Heitsch, Humboldt-Universität Berlin, Tel: 030-2093 5448,
Company:  GAMS Software GmbH, GAMS Development Corporation   
Period:   January - March 2002

Let a stochastic program with two or higher number of stages and an initial set of scenarios and their probabilities modeling the stochastic data process be given. The scenario reduction concept developed in [1] and the algorithms in [1,2] determine a subset of scenarios and the optimal redistribution of probabilities relative to the preserved scenarios. The concept is general and universal. No requirements on the stochastic data process (e.g. its probability distribution or its dimension) and on the structure of the scenarios (e.g. tree- or non-tree-structured) are imposed. The reduction algorithms require the following input:
- number of scenarios in the initial set,
- scenarios and their probabilities,
- number of scenarios to be preserved or relative accuracy of the reduced scenario set,
- (if available) model information (number of stages, stochasticity in objective and/or right hand sides and/or technology matrices)
The aim of the project is to implement the scenario reduction algorithms and to develop the software tool GAMS/SCENRED.

[1] J. Dupacova, N. Gröwe-Kuska, W. Römisch: Scenario reduction in stochastic programming: An approach using probability metrics. Mathematical Programming, Ser. A 95 (2003), 493-511 .

[2] H. Heitsch, W. Römisch: Scenario reduction algorithms in stochastic programming. Computational Optimization and Applications 24 (2003), 187-206.

Both papers are downloadable from

last modified January 2, 2003