Financial scenario generation for stochastic multi-stage decision processes as facility location problems. (English) Zbl 1144.90442

Summary: The quality of multi-stage stochastic optimization models as they appear in asset liability management, energy planning, transportation, supply chain management, and other applications depends heavily on the quality of the underlying scenario model, describing the uncertain processes influencing the profit/cost function, such as asset prices and liabilities, the energy demand process, demand for transportation, and the like. A common approach to generate scenarios is based on estimating an unknown distribution and matching its moments with moments of a discrete scenario model. This paper demonstrates that the problem of finding valuable scenario approximations can be viewed as the problem of optimally approximating a given distribution with some distance function. We show that for Lipschitz continuous cost/profit functions it is best to employ the Wasserstein distance. The resulting optimization problem can be viewed as a multi-dimensional facility location problem, for which at least good heuristic algorithms exist. For multi-stage problems, a scenario tree is constructed as a nested facility location problem. Numerical convergence results for financial mean-risk portfolio selection conclude the paper.


90B85 Continuous location
90C15 Stochastic programming
90C90 Applications of mathematical programming
91B28 Finance etc. (MSC2000)


Full Text: DOI


[1] Dupačová, J., G. Consigli, and S.W. Wallace. (2000). ”Generating Scenarios for Multistage Stochastic Programs.” Annals of Operations Research, 100, 25–53. · Zbl 1017.90068 · doi:10.1023/A:1019206915174
[2] Dupačová, J., N. Gröwe-Kuska, and W. Römisch. (2003). ”Scenario Reduction in Stochastic Programming: An Approach Using Probability Metrics.” Mathematical Programming, Series A, 95, 493–511. · Zbl 1023.90043 · doi:10.1007/s10107-002-0331-0
[3] Fourer, R., D. Gay, and B. Kernighan. (2002). AMPL: A Modeling Language for Mathematical Programming. Duxbury Press/Brooks/Cole Publishing Company. · Zbl 0701.90062
[4] Heitsch, H. and W. Römisch. (2003). ”Scenario Reduction Algorithms in Stochastic Programming.” Computational Optimization and Applications, 24(2–3), 187–206. · Zbl 1094.90024 · doi:10.1023/A:1021805924152
[5] Heyde, C. (1963). ”On the Property of the Lognormal Distribution.” Journal of the Royal Statistical Society, Series B, 25, 392–393. · Zbl 0114.33802
[6] Høyland, K. and S.W. Wallace. (2001). ”Generating Scenario Trees for Multistage Decision Problems.” Management Science, 47, 295–307. · Zbl 1232.91132 · doi:10.1287/mnsc.
[7] Koivu, M. (2005). ”Variance Reduction in Sample Approximations of Stochastic Programs.” Mathematical Programming, Series A, 103(3), 463–485. · Zbl 1099.90036 · doi:10.1007/s10107-004-0557-0
[8] Kouwenberg, R. (2001). ”Scenario Generation and Stochastic Programming Models for Asset Liability Management.” European Journal of Operation Research, 134, 279–292. · Zbl 1008.91050 · doi:10.1016/S0377-2217(00)00261-7
[9] Monge, G. (1781). ”Mémoire sur la théorie des déblais et remblais.” Hist. Acad. R. Sci. Paris.
[10] Pennanen, T. (2005). ”Epi-Convergent Discretizations of Multistage Stochastic Programs.” Mathematics of Operations Research, 30(1), 245–256. · Zbl 1082.90078 · doi:10.1287/moor.1040.0114
[11] Pennanen, T. and M. Koivu. (2005). ”Epi-Convergent Discretizations of Stochastic Programs via Integration Quadratures.” Numerische Mathematik, 100(1), 141–163. · Zbl 1063.65047 · doi:10.1007/s00211-004-0571-4
[12] Pflug, G. (2001). ”Scenario Tree Generation for Multiperiod Financial Optimization by Optimal Discretization.” Mathematical Programming, Series B, 89, 251–257. · Zbl 0987.91034 · doi:10.1007/PL00011398
[13] Rachev, S. and W. Römisch. (2002). ”Quantitative Stability in Stochastic Programming: The Method of Probability Metrics.” Mathematics of Operations Research, 27, 792–818. · Zbl 1082.90080 · doi:10.1287/moor.27.4.792.304
[14] Rachev, S.T. (1991). Probability Metrics and the Stability of Stochastic Models. New York: John Wiley and Sons. · Zbl 0744.60004
[15] Rüschendorf1998]RachevRueschendorf1998 Rachev, S.T. and L. Rüschendorf. (1998). Mass Transportation Problems. Vol. I, Probability and its Applications. New York: Springer-Verlag.
[16] Rockafellar, R. and S. Uryasev. (2000). ”Optimization of Conditional Value-at-Risk.” The Journal of Risk, 2(3), 21–41.
[17] Ruszczynski, A. and A. Shapiro (Eds.). (2003). Stochastic Programming, Vol. 10 of Handbooks in Operations Research and Management Science. Elsevier.
[18] Vallander, S. (1973). ”Calculation of the Wasserstein Distance Between Probability Distributions on the Line.” Theory of Probability and Its Applications, 18, 784–786. · Zbl 0351.60009 · doi:10.1137/1118101
[19] Wallace, S.W. and W.T. Ziemba (Eds.). (2005). Applications of Stochastic Programming, MPS-SIAM Series on Optimization. SIAM. · Zbl 1068.90002
[20] Zolotarev, V. (1983). ”Probability Metrics.” Theory of Probability and Its Applications, 28, 278–302. · Zbl 0533.60025 · doi:10.1137/1128025
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.