Experimental Study of Methods of Scenario Lattice Construction for Stochastic Dual Dynamic Programming  

作　　者：Dmitry Golembiovsky Anton Pavlov Smetanin Daniil Dmitry Golembiovsky;Anton Pavlov;Smetanin Daniil(Moscow State University, Moscow, Russia;New Economic School, Moscow, Russia)

机构地区：[1]Moscow State University, Moscow, Russia [2]New Economic School, Moscow, Russia

出　　处：《Open Journal of Optimization》2021年第2期47-60,共14页最优化（英文）

摘　　要：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.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.

关 键 词：Stochastic Dual Dynamic Programming Newsvendor Problem Markov Process 

分 类 号：O17[理学—数学]