×

zbMATH — the first resource for mathematics

Scenario tree reduction for multistage stochastic programs. (English) Zbl 1171.90485
Summary: A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the \(L_r\)-distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. An algorithm is presented for selecting and removing nodes of a scenario tree such that a prescribed error tolerance is met. Some numerical experience is reported.

MSC:
90C15 Stochastic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Casey M, Sen S (2005) The scenario generation algorithm for multistage stochastic linear programming. Math Oper Res 30: 615–631 · Zbl 1082.90076 · doi:10.1287/moor.1050.0146
[2] Dupačová J, Consigli G, Wallace SW (2000) Scenarios for multistage stochastic programs. Ann Oper Res 100: 25–53 · Zbl 1017.90068 · doi:10.1023/A:1019206915174
[3] Dupačová J, Gröwe-Kuska N, Römisch W (2003) Scenario reduction in stochastic programming: an approach using probability metrics. Math Program 95: 493–511 · Zbl 1023.90043 · doi:10.1007/s10107-002-0331-0
[4] Eichhorn A, Römisch W (2005) Polyhedral risk measures in stochastic programming. SIAM J Optim 16: 69–95 · Zbl 1114.90077 · doi:10.1137/040605217
[5] Eichhorn A, Römisch W (2006) Mean-risk optimization models for electricity portfolio management. In: Proceedings of PMAPS 2006 (Probabilistic Methods Applied to Power Systems), Stockholm, Sweden
[6] Eichhorn A, Römisch W (2008) Stability of multistage stochastic programs incorporating polyhedral risk measures. Optimization 57: 295–318 · Zbl 1192.90131 · doi:10.1080/02331930701779930
[7] Heitsch H, Römisch W (2003) Scenario reduction algorithms in stochastic programming. Comp Optim Appl 24: 187–206 · Zbl 1094.90024 · doi:10.1023/A:1021805924152
[8] Heitsch H, Römisch W (2006) Stability and scenario trees for multistage stochastic programs. In: Infanger G (ed) Stochastic Programming–The State of the Art (submitted) · Zbl 1251.90297
[9] Heitsch H, Römisch W (2007) A note on scenario reduction for two-stage stochastic programs. Oper Res Let 35: 731–736 · Zbl 1169.90420 · doi:10.1016/j.orl.2006.12.008
[10] Heitsch H, Römisch W (2008) Scenario tree modeling for multistage stochastic programs. Math Program (to appear) · Zbl 1173.90007
[11] Heitsch H, Römisch W, Strugarek C (2006) Stability of multistage stochastic programs. SIAM J Optim 17: 511–525 · Zbl 1165.90582 · doi:10.1137/050632865
[12] Henrion R, Küchler C, Römisch W (2007) Scenario reduction in stochastic programming with respect to discrepancy distances. Comp Optim Appl (to appear) · Zbl 1178.90258
[13] Henrion R, Küchler C, Römisch W (2008) Discrepancy distances and scenario reduction in two-stage stochastic integer programming. J Ind Manage Optim 4: 363–384 · Zbl 1161.90450
[14] Hochreiter R, Pflug GCh (2007) Financial scenario generation for stochastic multi-stage decision processes as facility location problems. Ann Oper Res 152: 257–272 · Zbl 1144.90442 · doi:10.1007/s10479-006-0140-6
[15] Høyland K, Kaut M, Wallace SW (2003) A heuristic for moment-matching scenario generation. Comp Optim Appl 24: 169–185 · Zbl 1094.90579 · doi:10.1023/A:1021853807313
[16] Kuhn D (2005) Generalized bounds for convex multistage stochastic programs. Lecture Notes in Economics and Mathematical Systems, vol 548. Springer, Berlin · Zbl 1103.90069
[17] Kuhn D (2008) Aggregation and discretization in multistage stochastic programming. Math Program 113: 61–94 · Zbl 1135.90032 · doi:10.1007/s10107-006-0048-6
[18] Pennanen T (2009) Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Math Program 116: 461–479 · Zbl 1165.90014 · doi:10.1007/s10107-007-0113-9
[19] Rachev ST, Rüschendorf L (1998) Mass transportation problems, vol I, II. Springer, Berlin
[20] Römisch W (2003) Stability of stochastic programming problems. In: Ruszczyński A, Shapiro A (eds) Stochastic programming, Handbooks in Operations Research and Management Science, vol 10. Elsevier, Amsterdam, pp 483–554
[21] Römisch W, Wets RJ-B (2007) Stability of \(\epsilon\)-approximate solutions to convex stochastic programs. SIAM J Optim 18: 961–979 · Zbl 1211.90151 · doi:10.1137/060657716
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.