{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:46:25Z","timestamp":1774946785899,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T00:00:00Z","timestamp":1600128000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T00:00:00Z","timestamp":1600128000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s10107-020-01567-1","type":"journal-article","created":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T13:03:45Z","timestamp":1600175025000},"page":"717-754","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Complexity of stochastic dual dynamic programming"],"prefix":"10.1007","volume":"191","author":[{"given":"Guanghui","family":"Lan","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,15]]},"reference":[{"key":"1567_CR1","unstructured":"Ahmed, S., Cabral, F.G., Costa, B.F.P.D.: Stochastic lipschitz dynamic programming (2019)"},{"key":"1567_CR2","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1039\/C9RE00176J","volume":"4","author":"H Bao","year":"2019","unstructured":"Bao, H., Zhou, Z., Kotsalis, G., Lan, G., Tong, Z.: Lignin valorization process control under feedstock uncertainty through a dynamic stochastic programming approach. React. Chem. Eng. 4, 1740\u20131747 (2019)","journal-title":"React. Chem. Eng."},{"key":"1567_CR3","unstructured":"Baucke, R., Downward, A., Zakeri, G.: A deterministic algorithm for solving multistage stochastic programming problems. Technical report, The University of Auckland, 70 Symonds Street, Grafton, Auckland, July 2017 (2017)"},{"issue":"5","key":"1567_CR4","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1287\/opre.33.5.989","volume":"33","author":"JR Birge","year":"1985","unstructured":"Birge, J.R.: Decomposition and partitioning methods for multistage stochastic linear programs. Oper. Res. 33(5), 989\u20131007 (1985)","journal-title":"Oper. Res."},{"key":"1567_CR5","volume-title":"Introduction to Stochastic Programming","author":"JR Birge","year":"1997","unstructured":"Birge, J.R., Louveaux, F.V.: Introduction to Stochastic Programming. Springer, New York (1997)"},{"issue":"1","key":"1567_CR6","first-page":"20","volume":"1","author":"CJ Donohue","year":"2006","unstructured":"Donohue, C.J., Birge, J.R.: The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse. Algorithm. Oper. Res. 1(1), 20 (2006)","journal-title":"Algorithm. Oper. Res."},{"issue":"3","key":"1567_CR7","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1287\/opre.2018.1835","volume":"67","author":"A Georghiou","year":"2019","unstructured":"Georghiou, A., Tsoukalas, A., Wiesemann, W.: Robust dual dynamic programming. Oper. Res. 67(3), 813\u2013830 (2019)","journal-title":"Oper. Res."},{"key":"1567_CR8","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1287\/moor.2014.0664","volume":"40","author":"P Girardeau","year":"2015","unstructured":"Girardeau, P., Leclere, V., Philpott, A.B.: On the convergence of decomposition methods for multistage stochastic convex programs. Math. Oper. Res. 40, 130\u2013145 (2015)","journal-title":"Math. Oper. Res."},{"key":"1567_CR9","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10589-013-9584-1","volume":"57","author":"V Guigues","year":"2014","unstructured":"Guigues, V.: Sddp for some interstage dependent risk-averse problems and application to hydro-thermal planning. Comput. Optim. Appl. 57, 167\u2013203 (2014)","journal-title":"Comput. Optim. Appl."},{"key":"1567_CR10","doi-asserted-by":"crossref","unstructured":"Guigues, V.: Inexact cuts in deterministic and stochastic dual dynamic programming applied to linear optimization problems (2018)","DOI":"10.2139\/ssrn.3102988"},{"key":"1567_CR11","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1287\/moor.16.3.650","volume":"16","author":"JL Higle","year":"1991","unstructured":"Higle, J.L., Sen, S.: Stochastic decomposition: an algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16, 650\u2013669 (1991)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1567_CR12","first-page":"2","volume":"6","author":"M Hindsberger","year":"2014","unstructured":"Hindsberger, M., Philpott, A.B.: Resa: a method for solving multistage stochastic linear programs. J. Appl. Oper. Res. 6(1), 2\u201315 (2014)","journal-title":"J. Appl. Oper. Res."},{"key":"1567_CR13","first-page":"703","volume":"8","author":"JE Kelley","year":"1960","unstructured":"Kelley, J.E.: The cutting plane method for solving convex programs. J. SIAM 8, 703\u2013712 (1960)","journal-title":"J. SIAM"},{"issue":"1\u20132","key":"1567_CR14","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s10107-014-0787-8","volume":"152","author":"V Kozm\u00edk","year":"2015","unstructured":"Kozm\u00edk, V., Morton, D.P.: Evaluating policies in risk-averse multi-stage stochastic programming. Math. Program. 152(1\u20132), 275\u2013300 (2015)","journal-title":"Math. Program."},{"key":"1567_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39568-1","volume-title":"First-Order and Stochastic Optimization Methods for Machine Learning","author":"G Lan","year":"2020","unstructured":"Lan, G.: First-Order and Stochastic Optimization Methods for Machine Learning. Springer, Basel (2020)"},{"key":"1567_CR16","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s10107-011-0442-6","volume":"134","author":"G Lan","year":"2012","unstructured":"Lan, G., Nemirovski, A.S., Shapiro, A.: Validation analysis of mirror descent stochastic approximation method. Math. Program. 134, 425\u2013458 (2012)","journal-title":"Math. Program."},{"key":"1567_CR17","unstructured":"Lan, G., Zhou, Z.: Dynamic stochastic approximation for multi-stage stochastic optimization. Manuscript, Georgia Institute of Technology, 2017. Mathematical Programming, under minor revision (2017)"},{"issue":"2","key":"1567_CR18","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1137\/19M1258876","volume":"30","author":"V Lecl\u00e8re","year":"2020","unstructured":"Lecl\u00e8re, V., Carpentier, P., Chancelier, J.P., Lenoir, A., Pacaud, F.: Exact converging bounds for stochastic dual dynamic programming via fenchel duality. SIAM J. Optim. 30(2), 1223\u20131250 (2020)","journal-title":"SIAM J. Optim."},{"key":"1567_CR19","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s10957-004-1842-z","volume":"125","author":"K Linowsky","year":"2005","unstructured":"Linowsky, K., Philpott, A.B.: On the convergence of sampling-based decomposition algorithms for multistage stochastic programs. J. Optim. Theory Appl. 125, 349\u2013366 (2005)","journal-title":"J. Optim. Theory Appl."},{"key":"1567_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"YE Nesterov","year":"2004","unstructured":"Nesterov, Y.E.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Norwell, MA (2004)"},{"issue":"1\u20133","key":"1567_CR21","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF01582895","volume":"52","author":"M Pereira","year":"1991","unstructured":"Pereira, M., Pinto, L.: Multi-stage stochastic optimization applied to energy planning. Math. Program. 52(1\u20133), 359\u2013375 (1991)","journal-title":"Math. Program."},{"key":"1567_CR22","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1287\/opre.2013.1175","volume":"61","author":"A Philpott","year":"2013","unstructured":"Philpott, A., Matos, Vd, Finardi, E.: On solving multistage stochastic programs with coherent risk measures. Oper. Res. 61, 957\u2013970 (2013)","journal-title":"Oper. Res."},{"key":"1567_CR23","unstructured":"Philpott, A., Wahid, F., Bonnans, F.: Midas: A mixed integer dynamic approximation scheme, 2016. PhD thesis, Inria Saclay Ile de France (2016)"},{"issue":"1","key":"1567_CR24","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1287\/moor.16.1.119","volume":"16","author":"R Tyrrell Rockafellar","year":"1991","unstructured":"Tyrrell Rockafellar, R., Wets, Roger J.-B.: Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1), 119\u2013147 (1991)","journal-title":"Math. Oper. Res."},{"key":"1567_CR25","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0927-0507(03)10003-5","volume-title":"Stochastic Programming","author":"A Ruszczy\u0144ski","year":"2003","unstructured":"Ruszczy\u0144ski, A.: Decomposition methods. In: Ruszczy\u0144ski, A., Shapiro, A. (eds.) Stochastic Programming, pp. 141\u2013211. Elsevier, Amsterdam (2003)"},{"key":"1567_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.orl.2005.02.003","volume":"34","author":"A Shapiro","year":"2006","unstructured":"Shapiro, A.: On complexity of multistage stochastic programs. Oper. Res. Lett. 34, 1\u20138 (2006)","journal-title":"Oper. Res. Lett."},{"key":"1567_CR27","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.: Analysis of stochastic dual dynamic programming method. Eur. J. Oper. Res. 209, 63\u201372 (2011)","journal-title":"Eur. J. Oper. Res."},{"key":"1567_CR28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718751","volume-title":"Lectures on Stochastic Programming: Modeling and Theory","author":"A Shapiro","year":"2009","unstructured":"Shapiro, A., Dentcheva, D., Ruszczy\u0144ski, A.: Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia (2009)"},{"key":"1567_CR29","unstructured":"Shapiro, A., Nemirovski, A.: On complexity of stochastic programming problems. E-print available at:\u00a0http:\/\/www.optimization-online.org (2004)"},{"issue":"1\u20132","key":"1567_CR30","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s10107-018-1249-5","volume":"175","author":"J Zou","year":"2019","unstructured":"Zou, J., Ahmed, S., Sun, X.A.: Stochastic dual dynamic integer programming. Math. Program. 175(1\u20132), 461\u2013502 (2019)","journal-title":"Math. Program."}],"updated-by":[{"DOI":"10.1007\/s10107-022-01798-4","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,3,11]],"date-time":"2022-03-11T00:00:00Z","timestamp":1646956800000}}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01567-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01567-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01567-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,11]],"date-time":"2022-03-11T16:43:42Z","timestamp":1647017022000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01567-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,15]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["1567"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01567-1","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s10107-022-01798-4","asserted-by":"object"}]},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,15]]},"assertion":[{"value":"22 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2022","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\/s10107-022-01798-4","URL":"https:\/\/doi.org\/10.1007\/s10107-022-01798-4","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}