Jitka Dupacov, Nicole Gröwe-Kuska, Werner Römisch
Preprint series: Institut für Mathematik, Humboldt-Universität
zu Berlin (ISSN 0863-0976), 09, 20
MSC 2000
-
90C15 Stochastic programming
-
90C31 Sensitivity, stability, parametric optimization
Abstract
Given
a convex stochastic programming problem with a discrete initial probability
distribution, the problem of optimal scenario reduction is stated as follows:
Determine a scenario subset of prescribed cardinality and a probability
measure based on this set that is closest to the initial distribution in
terms of a natural (or canonical) probability metric. Arguments from stability
analysis indicate that Fortet-Mourier type probability metrics may serve
as such canonical metrics. Efficient algorithms are developed that determine
optimal reduced measures approximately. Numerical experience is reported
for reductions of electrical load scenario trees for power management under
uncertainty. For instance, it turns out that after a 50% reduction of the
scenario tree the optimal reduced tree still has about 90% of relative
accuracy.
Keywords:
Stochastic programming, quantitative stability, Fortet-Mourier metrics,
scenario reduction, transportation problem, electrical load scenario tree