{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T20:42:44Z","timestamp":1777149764407,"version":"3.51.4"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,8,24]],"date-time":"2021-08-24T00:00:00Z","timestamp":1629763200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,24]],"date-time":"2021-08-24T00:00:00Z","timestamp":1629763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007370","name":"Universit\u00e9 Catholique de Louvain","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007370","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["864537"],"award-info":[{"award-number":["864537"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Manag Sci"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study different parallelization schemes for the stochastic dual dynamic programming (SDDP) algorithm. We propose a taxonomy for these parallel algorithms, which is based on the concept of parallelizing by scenario and parallelizing by node of the underlying stochastic process. We develop a synchronous and asynchronous version for each configuration. The parallelization strategy in the parallelscenario configuration aims at parallelizing the Monte Carlo sampling procedure in the forward pass of the SDDP algorithm, and thus generates a large number of supporting hyperplanes in parallel. On the other hand, the parallel-node strategy aims at building a single hyperplane of the dynamic programming value function in parallel. The considered algorithms are implemented using Julia and JuMP on a high performance computing cluster. We study the effectiveness of the methods in terms of achieving tight optimality gaps, as well as the scalability properties of the algorithms with respect to an increasing number of CPUs. In particular, we study the effects of the different parallelization strategies on performance when increasing the number of Monte Carlo samples in the forward pass, and demonstrate through numerical experiments that such an increase may be harmful. Our results indicate that a parallel-node strategy presents certain benefits as compared to a parallel-scenario configuration.<\/jats:p>","DOI":"10.1007\/s10287-021-00411-x","type":"journal-article","created":{"date-parts":[[2021,8,24]],"date-time":"2021-08-24T17:07:14Z","timestamp":1629824834000},"page":"199-226","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Parallel and distributed computing for stochastic dual dynamic programming"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4590-2254","authenticated-orcid":false,"given":"D.","family":"\u00c1vila","sequence":"first","affiliation":[]},{"given":"A.","family":"Papavasiliou","sequence":"additional","affiliation":[]},{"given":"N.","family":"L\u00f6hndorf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,24]]},"reference":[{"key":"411_CR1","doi-asserted-by":"crossref","unstructured":"Aravena I, Papavasiliou A (2020) Asynchronous lagrangian scenario decomposition. Mathematical Programming Computation pp 1\u201350","DOI":"10.1007\/s12532-020-00185-4"},{"key":"411_CR2","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1109\/TPAS.1970.292595","volume":"2","author":"NV Arvanitidits","year":"1970","unstructured":"Arvanitidits NV, Rosing J (1970) Composite representation of a multireservoir hydroelectric power system. IEEE Trans Power Appar Syst 2:319\u2013326","journal-title":"IEEE Trans Power Appar Syst"},{"issue":"1","key":"411_CR3","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1137\/16M1072231","volume":"28","author":"T Asamov","year":"2018","unstructured":"Asamov T, Powell WB (2018) Regularized decomposition of high-dimensional multistage stochastic programs with markov uncertainty. SIAM J Optim 28(1):575\u2013595","journal-title":"SIAM J Optim"},{"key":"411_CR4","unstructured":"Bertsekas DP, Tsitsiklis JN (1989) Parallel and distributed computation: numerical methods, vol 23. Prentice hall Englewood Cliffs, NJ"},{"key":"411_CR5","doi-asserted-by":"crossref","unstructured":"Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing.","DOI":"10.1137\/141000671"},{"key":"411_CR7","doi-asserted-by":"crossref","unstructured":"Birge JR, Louveaux F (2011) Introduction to stochastic programming. Springer Science & Business Media","DOI":"10.1007\/978-1-4614-0237-4"},{"issue":"8","key":"411_CR31","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1109\/TPDS.2003.1225052","volume":"14","author":"EL da Silva","year":"2003","unstructured":"da Silva EL, Finardi EC (2003) Parallel processing applied to the planning of hydrothermal systems. IEEE Trans Parallel Distrib Syst 14(8):721\u2013729","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"411_CR8","volume-title":"Solving long-term hydro-thermal scheduling problems","author":"V De Matos","year":"2010","unstructured":"De Matos V, Philpott AB, Finardi EC, Guan Z (2010) Solving long-term hydro-thermal scheduling problems. Technical report, Electric Power Optimization Centre, University of Auckland, Tech. rep."},{"key":"411_CR9","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/j.cam.2015.04.048","volume":"290","author":"VL De Matos","year":"2015","unstructured":"De Matos VL, Philpott AB, Finardi EC (2015) Improving the performance of stochastic dual dynamic programming. J Comput Appl Math 290:196\u2013208","journal-title":"J Comput Appl Math"},{"key":"411_CR10","doi-asserted-by":"crossref","unstructured":"Dowson O, Kapelevich L (2021) Sddp. jl: a julia package for stochastic dual dynamic programming. INFORMS Journal on Computing 33(1):27\u201333","DOI":"10.1287\/ijoc.2020.0987"},{"issue":"3","key":"411_CR11","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1016\/j.ejor.2018.10.033","volume":"274","author":"O Dowson","year":"2019","unstructured":"Dowson O, Philpott A, Mason A, Downward A (2019) A multi-stage stochastic optimization model of a pastoral dairy farm. Eur J Oper Res 274(3):1077\u20131089","journal-title":"Eur J Oper Res"},{"issue":"2","key":"411_CR12","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1137\/15M1020575","volume":"59","author":"I Dunning","year":"2017","unstructured":"Dunning I, Huchette J, Lubin M (2017) Jump: A modeling language for mathematical optimization. SIAM Rev 59(2):295\u2013320. https:\/\/doi.org\/10.1137\/15M1020575","journal-title":"SIAM Rev"},{"issue":"2","key":"411_CR13","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1049\/iet-gtd.2009.0107","volume":"4","author":"B Flach","year":"2010","unstructured":"Flach B, Barroso L, Pereira M (2010) Long-term optimal allocation of hydro generation for a price-maker company in a competitive market: latest developments and a stochastic dual dynamic programming approach. IET Gener Transm Distrib 4(2):299\u2013314","journal-title":"IET Gener Transm Distrib"},{"issue":"1","key":"411_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.ejor.2016.10.047","volume":"258","author":"V Guigues","year":"2017","unstructured":"Guigues V (2017) Dual dynamic programing with cut selection: Convergence proof and numerical experiments. Eur J Oper Res 258(1):47\u201357","journal-title":"Eur J Oper Res"},{"key":"411_CR15","unstructured":"Guigues V, Bandarra M (2019) Single cut and multicut sddp with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments. arXiv preprint arXiv:190206757"},{"issue":"12","key":"411_CR16","doi-asserted-by":"publisher","first-page":"14287","DOI":"10.3390\/en81212431","volume":"8","author":"A Helseth","year":"2015","unstructured":"Helseth A, Braaten H (2015) Efficient parallelization of the stochastic dual dynamic programming algorithm applied to hydropower scheduling. Energies 8(12):14287\u201314297","journal-title":"Energies"},{"key":"411_CR17","doi-asserted-by":"crossref","unstructured":"Kaneda T, Scieur D, Cambier L, Henneaux P (2018) Optimal management of storage for offsetting solar power uncertainty using multistage stochastic programming. In: 2018 Power Systems Computation Conference (PSCC), IEEE, pp 1\u20137","DOI":"10.23919\/PSCC.2018.8443062"},{"issue":"2","key":"411_CR18","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1016\/j.ejor.2018.08.001","volume":"273","author":"N L\u00f6hndorf","year":"2019","unstructured":"L\u00f6hndorf N, Shapiro A (2019) Modeling time-dependent randomness in stochastic dual dynamic programming. Eur J Oper Res 273(2):650\u2013661","journal-title":"Eur J Oper Res"},{"key":"411_CR19","doi-asserted-by":"crossref","unstructured":"L\u00f6hndorf N, Wozabal D (2020) Gas storage valuation in incomplete markets. European Journal of Operational Research","DOI":"10.1016\/j.ejor.2020.05.044"},{"issue":"4","key":"411_CR20","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1287\/opre.2013.1182","volume":"61","author":"N L\u00f6hndorf","year":"2013","unstructured":"L\u00f6hndorf N, Wozabal D, Minner S (2013) Optimizing trading decisions for hydro storage systems using approximate dual dynamic programming. Oper Res 61(4):810\u2013823","journal-title":"Oper Res"},{"key":"411_CR21","doi-asserted-by":"crossref","unstructured":"Machado FD, Diniz AL, Borges CL, Brand\u00e3o LC (2021) Asynchronous parallel stochastic dual dynamic programming applied to hydrothermal generation planning. Electric Power Systems Research 191:106907","DOI":"10.1016\/j.epsr.2020.106907"},{"issue":"3","key":"411_CR22","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1109\/TPWRS.2014.2341354","volume":"30","author":"A Papavasiliou","year":"2014","unstructured":"Papavasiliou A, Oren SS, Rountree B (2014) Applying high performance computing to transmissionconstrained stochastic unit commitment for renewable energy integration. IEEE Trans Power Syst 30(3):1109\u20131120","journal-title":"IEEE Trans Power Syst"},{"issue":"2","key":"411_CR23","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1109\/TSTE.2017.2748463","volume":"9","author":"A Papavasiliou","year":"2017","unstructured":"Papavasiliou A, Mou Y, Cambier L, Scieur D (2017) Application of stochastic dual dynamic programming to the real-time dispatch of storage under renewable supply uncertainty. IEEE Transactions on Sustainable Energy 9(2):547\u2013558","journal-title":"IEEE Transactions on Sustainable Energy"},{"issue":"1\u20133","key":"411_CR24","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF01582895","volume":"52","author":"MV Pereira","year":"1991","unstructured":"Pereira MV, Pinto LM (1991) Multi-stage stochastic optimization applied to energy planning. Math Program 52(1\u20133):359\u2013375","journal-title":"Math Program"},{"issue":"2","key":"411_CR25","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/j.ejor.2011.10.056","volume":"218","author":"AB Philpott","year":"2012","unstructured":"Philpott AB, De Matos VL (2012) Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion. Eur J Oper Res 218(2):470\u2013483","journal-title":"Eur J Oper Res"},{"issue":"4","key":"411_CR26","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1016\/j.orl.2008.01.013","volume":"36","author":"AB Philpott","year":"2008","unstructured":"Philpott AB, Guan Z (2008) On the convergence of stochastic dual dynamic programming and related methods. Oper Res Lett 36(4):450\u2013455","journal-title":"Oper Res Lett"},{"issue":"3\u20134","key":"411_CR27","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s10287-018-0314-0","volume":"15","author":"AB Philpott","year":"2018","unstructured":"Philpott AB, de Matos VL, Kapelevich L (2018) Distributionally robust sddp. CMS 15(3\u20134):431\u2013454","journal-title":"CMS"},{"issue":"4","key":"411_CR28","doi-asserted-by":"publisher","first-page":"4888","DOI":"10.1109\/TPWRS.2012.2236654","volume":"28","author":"RJ Pinto","year":"2013","unstructured":"Pinto RJ, Borges CT, Maceira ME (2013) An efficient parallel algorithm for large scale hydrothermal system operation planning. IEEE Trans Power Syst 28(4):4888\u20134896","journal-title":"IEEE Trans Power Syst"},{"issue":"1","key":"411_CR29","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.ejor.2010.08.007","volume":"209","author":"A Shapiro","year":"2011","unstructured":"Shapiro A (2011) Analysis of stochastic dual dynamic programming method. Eur J Oper Res 209(1):63\u201372","journal-title":"Eur J Oper Res"},{"issue":"2","key":"411_CR30","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/j.ejor.2012.08.022","volume":"224","author":"A Shapiro","year":"2013","unstructured":"Shapiro A, Tekaya W, da Costa JP, Soares MP (2013) Risk neutral and risk averse stochastic dual dynamic programming method. Eur J Oper Res 224(2):375\u2013391","journal-title":"Eur J Oper Res"},{"issue":"1","key":"411_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10589-019-00104-x","volume":"74","author":"W Van Ackooij","year":"2019","unstructured":"Van Ackooij W, de Oliveira W, Song Y (2019) On level regularization with normal solutions in decomposition methods for multistage stochastic programming problems. Comput Optim Appl 74(1):1\u201342","journal-title":"Comput Optim Appl"}],"updated-by":[{"DOI":"10.1007\/s10287-021-00417-5","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T00:00:00Z","timestamp":1636934400000}}],"container-title":["Computational Management Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-021-00411-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10287-021-00411-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10287-021-00411-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T20:27:11Z","timestamp":1652905631000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10287-021-00411-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,24]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["411"],"URL":"https:\/\/doi.org\/10.1007\/s10287-021-00411-x","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s10287-021-00417-5","asserted-by":"object"}]},"ISSN":["1619-697X","1619-6988"],"issn-type":[{"value":"1619-697X","type":"print"},{"value":"1619-6988","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,24]]},"assertion":[{"value":"10 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 November 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10287-021-00417-5","URL":"https:\/\/doi.org\/10.1007\/s10287-021-00417-5","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}