×

Aggregation and discretization in multistage stochastic programming. (English) Zbl 1135.90032

Summary: Multistage stochastic programs have applications in many areas and support policy makers in finding rational decisions that hedge against unforeseen negative events. In order to ensure computational tractability, continuous-state stochastic programs are usually discretized; and frequently, the curse of dimensionality dictates that decision stages must be aggregated. In this article we construct two discrete, stage-aggregated stochastic programs which provide upper and lower bounds on the optimal value of the original problem. The approximate problems involve finitely many decisions and constraints, thus principally allowing for numerical solution.

MSC:

90C15 Stochastic programming
90C25 Convex programming
49M29 Numerical methods involving duality

Software:

EVPI
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ash R. (1972) Real Analysis and Probability. Probability and Mathematical Statistics. Academic, Berlin Heidelberg Newyork · Zbl 0249.28001
[2] Birge J. (1984) Aggregation in stochastic production models. In: Proceedings of the 11th IFIP Conference on System Modelling and Optimization. Springer Berlin Heidelberg Newyork, New York · Zbl 0548.90033
[3] Birge J. (1985) Aggregation in stochastic linear programming. Math. Program. 31, 25–41 · Zbl 0562.90066 · doi:10.1007/BF02591859
[4] Birge, J., Louveaux, F.: Introduction to Stochastic Programming. Springer Berlin Heidelberg New York (1997) · Zbl 0892.90142
[5] Birge J., Wets R.B. (1987) Computing bounds for stochastic programming problems by means of a generalized moment problem. Math. Oper. Res. 12, 149–162 · Zbl 0619.90053 · doi:10.1287/moor.12.1.149
[6] Casey M., Sen S. (2005) The scenario generation algorithm for multistage stochastic linear programming. Math. Oper. Res. 30(3): 615–631 · Zbl 1082.90076 · doi:10.1287/moor.1050.0146
[7] Chow Y., Teicher H. (1997) Probability Theory, 3rd edn. Springer Berlin Heidelberg, New York · Zbl 0891.60002
[8] Dantzig G., Infanger G. (1992) Large-scale stochastic linear programs–importance sampling and Benders decomposition. Comput. Appl. Math. I: 111–120 · Zbl 0781.65052
[9] Dawid A. (1980) Conditional independence for statistical operations. Ann. Stat. 8(3): 598–617 · Zbl 0434.62006 · doi:10.1214/aos/1176345011
[10] Dempster M., Thompson R. (1999) EVPI-based importance sampling solution procedures for multistage stochastic linear programmes on parallel MIMD architectures. Ann. Oper. Res. 90, 161–184 · Zbl 0937.90075 · doi:10.1023/A:1018956530304
[11] Dupačová J., Gröwe-Kuska N., Römisch W. (2003) Scenario reduction in stochastic programming: an approach using probability metrics. Math. Program. Ser. A 95, 493–511 · Zbl 1023.90043 · doi:10.1007/s10107-002-0331-0
[12] Edirisinghe N., Ziemba W. (1994) Bounding the expectation of a saddle function with application to stochastic programming. Math. Oper. Res. 19, 314–340 · Zbl 0824.90101 · doi:10.1287/moor.19.2.314
[13] Edirisinghe N., Ziemba W. (1994) Bounds for two-stage stochastic programs with fixed recourse. Math. Oper. Res. 19, 292–313 · Zbl 0824.90100 · doi:10.1287/moor.19.2.292
[14] Ermoliev Y., Gaivoronski A. (1992) Stochastic quasigradient methods for optimization of discrete event systems. Ann. Oper. Res. 39, 1–39 · Zbl 0765.90069 · doi:10.1007/BF02060934
[15] Flåm S., Wets R.B. (1986) Finite horizon approximates of infinite horizon stochastic programs. Stochas. Optim. 81, 337–350 · Zbl 0596.90070
[16] Flåm S., Wets R.B. (1987) Existence results and finite horizon approximates for infinite horizon optimization problems. Econometrica 55, 1187–1209 · Zbl 0635.90098 · doi:10.2307/1911267
[17] Frauendorfer K. (1988) Solving SLP recourse problems with arbitrary multivariate distributions – the dependent case. Math. Oper. Res. 13, 377–394 · Zbl 0652.90080 · doi:10.1287/moor.13.3.377
[18] Frauendorfer K. (1992) Stochastic two-stage programming, Lect. Notes Econ. Math. Syst., vol. 392 Springer, Berlin Heidelberg Newyork · Zbl 0794.90042
[19] Frauendorfer K. (1994) Multistage stochastic programming: Error analysis for the convex case. Z. Oper. Res. 39(1): 93–122 · Zbl 0810.90098
[20] Frauendorfer K. (1996) Barycentric scenario trees in convex multistage stochastic programming. Math. Program. 75(2): 277–294 · Zbl 0874.90144
[21] Gassmann H., Ziemba W. (1986) A tight upper bound for the expectation of a convex function of a multivariate random variable. Math. Program. Study 27, 39–53 · Zbl 0603.60014
[22] Haarbrücker, G., Kuhn, D.: Valuation of electricity swing options by multistage stochastic programming. Working paper (2004) · Zbl 1177.90299
[23] Heitsch H., Römisch W. (2003) Scenario reduction algorithms in stochastic programming. Comput. Optim. Appl. 24, 187–206 · Zbl 1094.90024 · doi:10.1023/A:1021805924152
[24] Higle J., Sen S. (1991) Stochastic decomposition: An algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16, 650 fb–669 · Zbl 0746.90045 · doi:10.1287/moor.16.3.650
[25] Høyland K., Wallace S. (2001) Generating scenario trees for multistage decision problems. Manage. Sci. 47(2): 295–307 · Zbl 1232.91132 · doi:10.1287/mnsc.47.2.295.9834
[26] Infanger G. (1994) Planning under Uncertainty: Solving Large-Scale Stochastic Linear Programs. Boyd and Fraser, Danvers · Zbl 0867.90086
[27] Kall P. (1991) An upper bound for SLP using first and total second moments. Ann. Oper. Res. 30, 267–276 · Zbl 0749.90055 · doi:10.1007/BF02204820
[28] Kall P., Wallace S. (1994) Stochastic Programming. Wiley, Chichester
[29] Kaut, M., Wallace, S.: Evaluation of scenario-generation methods for stochastic programming. The Stochastic Programming E-Print Series (SPEPS) (2003) · Zbl 1171.90490
[30] Korf, L.: An approximation framework for infinite horizon stochastic dynamic optimization problems with discounted cost. Research report, Department of Mathematics, Washington University, Seattle, USA (2000) · Zbl 0971.90101
[31] Kuhn D. (2004) Generalized Bounds for Convex Multistage Stochastic Programs. Lect. Notes Econ. Math. Syst., vol. 548.Springer, Berlin Heidelberg Newyork · Zbl 1103.90069
[32] Madansky A. (1960) Inequalities for stochastic linear programming problems. Manage. Sci. 6, 197–204 · Zbl 0995.90601 · doi:10.1287/mnsc.6.2.197
[33] Meyn S., Tweedie R. (1996) Markov Chains and Stochastic Stability. Springer, Berlin Heidelberg New York · Zbl 0925.60001
[34] Pearl J. (1991) Probabilistic Reasoning in Intelligent Systems, 2nd edn. Morgan Kaufman, San Mateo · Zbl 0746.68089
[35] Pflug G. (2001) Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Program., Ser. B 89, 251–271 · Zbl 0987.91034 · doi:10.1007/PL00011398
[36] Prékopa A. (1995) Stochastic Programming. Kluwer, Dordrecht
[37] Rachev S., Römisch W. (2002) Quantitative stability in stochastic programming: the method of probability metrics. Math. Oper. Res. 27, 792–818 · Zbl 1082.90080 · doi:10.1287/moor.27.4.792.304
[38] Rockafellar R., Wets R.B. (1978) The optimal recourse problem in discrete time: L 1-multipliers for equality constraints. SIAM J. Control Optim. 16, 16–36 · Zbl 0397.90078 · doi:10.1137/0316002
[39] Schervish, M.: Theory of Statistics. Springer Berlin Heidelberg New York (1995) · Zbl 0834.62002
[40] Shapiro A. (2006) On complexity of multistage stochastic programs. Oper. Res. Lett. 34, 1–8 · Zbl 1080.90056 · doi:10.1016/j.orl.2005.02.003
[41] Shapiro A., Nemirovski A. (2005) On complexity of stochastic programming problems. In: Jeyakumar V., Rubinov A. (eds) Continuous Optimization: Current Trends and Applications, pp. 111–144. Springer Berlin Heidelberg Newyork · Zbl 1115.90041
[42] Verma, T., Pearl, J.: Causal networks and expressiveness. In: Proceedings of the 4th Workshop on Uncertainty in Artificial Intelligence, pp. 352–359. Mountain View, CA (1988)
[43] Dupačová (as Žáčková) J. (1966) On minimax solutions of stochastic linear programming problems. časopis pro Pěstování Matematiky 91, 423–429
[44] Wright S. (1994) Primal-dual aggregation and disaggregation for stochastic linear programs. Math. Oper. Res. 19(4): 893–908 · Zbl 0821.90086 · doi:10.1287/moor.19.4.893
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.