The stochastic dual dynamic programming (SDDP) algorithm is becoming increasingly used. In this paper we present analysis of different methods of lattice construction for SDDP exemplifying a realistic variant of the newsvendor problem, incorporating storage of production. We model several days of work and compare the profits realized using different methods of the lattice construction and the corresponding computer time spent in lattice construction. Our case differs from the known one because we consider not only a multidimensional but also a multistage case with stage dependence. We construct scenario lattice for different Markov processes which play a crucial role in stochastic modeling. The novelty of our work is comparing different methods of scenario lattice construction. We considered a realistic variant of the newsvendor problem. The results presented in this article show that the Voronoi method slightly outperforms others, but the k-means method is much faster overall.
References
[1]
Pereira, M.V.F. and Pinto, L.M.V.G. (1991) Multi-Stage Stochastic Optimization Applied to Energy Planning. Mathematical Programming, 52, 359–375. https://doi.org/10.1007/BF01582895
[2]
Dentcheva, D. and Ruszczynski, A. (2009) Lectures on Stochastic Programming. Modeling and Theory. Society for Industrial Mathematics, 9, 271-279.
[3]
Birge, J.R. and Louveaux, F. (2011) Introduction to Stochastic Programming. Springer, NewYork. https://doi.org/10.1007/978-1-4614-0237-4
[4]
Higle, J. L. (1998) Variance Reduction and Objective Function Evaluation in Stochastic Linear Programs. INFORMS Journal on Computing, 10, 121-260. https://doi.org/10.1287/ijoc.10.2.236
[5]
Kaut, M. and Wallace, S. (2007) Evaluation of Scenario-Generation Methods for Stochastic Programming. Pacific Journal of Optimization, 3, 257-271.
[6]
Roemich, W. and Heitsch, H. (2009) Scenario Tree Modelling for Multi-Stage Stochastic Programs. Mathematical Programming, 118, 371-406. https://doi.org/10.1007/s10107-007-0197-2
[7]
Vazsonyi, M. (2006) Overview of Scenario Tree Generation Methods, Applied in Financial and Economic Decision Making. Periodica Polytechnica Social and Management Sciences, 14, 29-37. https://doi.org/10.3311/pp.so.2006-1.04
[8]
Löhndorf, N. (2016) An Empirical Analysis of Scenario Generation Methods for Stochastic Optimization. European Journal of Operational Research, 255, 121-132. https://doi.org/10.1016/j.ejor.2016.05.021
[9]
Shapiro, A. (2013) Sample Average Approximation. In: Gass, S.I. and Fu, M.C., Eds., Encyclopedia of Operations Research and Management Science, Springer, Boston, MA, 1350-1355. https://doi.org/10.1007/978-1-4419-1153-7_1154
[10]
Shapiro, A. (2003) Monte Carlo Sampling Methods. Handbooks in Operations Research and Management Science, 10, 353-425. https://doi.org/10.1016/S0927-0507(03)10006-0
[11]
Glasserman, P. (2004) Monte Carlo Methods in Financial Engineering. Springer, NewYork. https://doi.org/10.1007/978-0-387-21617-1
[12]
Pflug, G.C. (2001) Scenario Tree Generation for Multiperiod Financial Optimization by Optimal Discretization. Mathematical Programming, 89, 251-271. https://doi.org/10.1007/PL00011398
[13]
Arthur, D. and Vassilvitskii, S. (2007) K-means++: The Advantages of Careful Seeding. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, 7-9 January 2007, 1027-1035.
[14]
Dowson, O. and Kapelevich, L. (2020) SDDP.jl: A Julia Package for Stochastic Dual Dynamic Programming. INFORMS Journal on Computing, 33, 1-418. https://doi.org/10.1287/ijoc.2020.0987
