×

A scalable bounding method for multistage stochastic programs. (English) Zbl 1372.49039

Summary: Many dynamic decision problems involving uncertainty can be appropriately modeled as multistage stochastic programs. However, most practical instances are so large and/or complex that it is impossible to solve them on a single computer, especially due to memory limitations. Extending the work of B. Sandıkçı et al. [Math. Program. 138, No. 1–2 (A), 253–272 (2013; Zbl 1266.90133)] on two-stage stochastic mixed-integer programs, this paper considers general multistage stochastic programs and develops a bounding method based on scenario decomposition. This method is broadly applicable, as it does not assume any problem structure including convexity. Moreover, it naturally fits into a distributed computing environment. Computational experiments with large-scale instances (with up to 100 million scenarios, about 1.5 billion decision variables – 85% binary – and 800 million constraints) demonstrate that the proposed method scales nicely with problem size and has immense potential to obtain high-quality solutions to practical instances within a reasonable time frame.

MSC:

49M27 Decomposition methods
68W10 Parallel algorithms in computer science
90C06 Large-scale problems in mathematical programming
90C11 Mixed integer programming
90C15 Stochastic programming
90C25 Convex programming
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Citations:

Zbl 1266.90133
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Ahmed, {\it A scenario decomposition algorithm for 0-1 stochastic programs}, Oper. Res. Lett., 41 (2013), pp. 565-569. · Zbl 1287.90041
[2] S. Ahmed and R. Garcia, {\it Dynamic capacity acquisition and assignment under uncertainty}, Ann. Oper. Res., 124 (2003), pp. 267-283. · Zbl 1053.90097
[3] S. Ahmed and N. V. Sahinidis, {\it An approximation scheme for stochastic integer programs arising in capacity expansion}, Oper. Res., 51 (2003), pp. 461-471. · Zbl 1163.90677
[4] J. R. Birge, {\it The value of the stochastic solution in stochastic linear programs with fixed recourse}, Math. Program., 24 (1982), pp. 314-325. · Zbl 0502.90065
[5] J. R. Birge and F. V. Louveaux, {\it Introduction to Stochastic Programming}, 2nd ed., Springer, New York, 2011. · Zbl 1223.90001
[6] J. R. Birge and R. J. B. Wets, {\it Sublinear upper bounds for stochastic programs with recourse}, Math. Program., 43 (1989), pp. 131-149. · Zbl 0663.90063
[7] N. Boland, I. Bak\ir, B. Dandurand, and A. Erera, {\it Scenario set partition dual bounds for multistage stochastic programming: A hierarchy of bounds and a partition sampling approach}, Optimization Online, 2016. · Zbl 07284459
[8] C. C. Carøe and R. Schultz, {\it Dual decomposition in stochastic integer programming}, Oper. Res. Lett., 24 (1999), pp. 37-45. · Zbl 1063.90037
[9] T. G. Crainic, M. Hewitt, and W. Rei, {\it Scenario grouping in a progressive hedging-based meta-heuristic for stochastic network design}, Computers Oper. Res., 43 (2014), pp. 90-99. · Zbl 1348.90165
[10] S. P. Dokov and D. P. Morton, {\it Second-order lower bounds on the expectation of a convex function}, Math. Oper. Res., 30 (2005), pp. 662-677. · Zbl 1082.90077
[11] N. C. P. Edirisinghe, {\it New second-order bounds on the expectation of saddle functions with applications to stochastic linear programming}, Oper. Res., 44 (1996), pp. 909-922. · Zbl 0879.90151
[12] H. P. Edmundson, {\it Bounds on the Expectation of a Convex Function of a Random Variable}, Tech. report, RAND Corporation, Santa Monica, CA, 1956.
[13] S. A. Erdogan and B. T. Denton, {\it Dynamic appointment scheduling with uncertain demand}, INFORMS J. Comput., 25 (2013), pp. 116-132.
[14] L. Escudero, A. Garin, M. Merino, and G. Pérez, {\it The value of the stochastic solution in multistage problems}, TOP, 15 (2007), pp. 48-64. · Zbl 1120.60064
[15] K. Frauendorfer, {\it Barycentric scenario trees in convex multistage stochastic programming}, Math. Program., 75 (1996), pp. 277-293. · Zbl 0874.90144
[16] A. A. Gaivoronski, {\it Stochastic optimization problems in telecommunications}, in Applications of Stochastic Programming, S. W. Wallece and W. T. Ziemba, eds., SIAM, Philadelphia, PA, 2005, pp. 669-701. · Zbl 1137.90629
[17] Y. Guan, S. Ahmed, and G. L. Nemhauser, {\it Cutting planes for multistage stochastic integer programs}, Oper. Res., 57 (2009), pp. 287-298. · Zbl 1181.90199
[18] H. Heitsch and W. Römisch, {\it Scenario tree modeling for multistage stochastic programs}, Math. Program., 118 (2009), pp. 371-406. · Zbl 1173.90007
[19] H. Heitsch and W. Römisch, {\it Scenario tree reduction for multistage stochastic programs}, Comput. Manag. Sci., 6 (2009), pp. 117-133. · Zbl 1171.90485
[20] H. Heitsch and W. Römisch, {\it Scenario tree generation for multi-stage stochastic programs}, in Stochastic Optimization Methods in Finance and Energy, M. Bertocchi, G. Consigli, and M. A. Dempster, eds., Springer, New York, 2011, pp. 313-341. · Zbl 1405.90089
[21] J. L. Higle and S. Sen, {\it Stochastic decomposition: An algorithm for two-stage linear programs with recourse}, Math. Oper. Res., 16 (1991), pp. 650-669. · Zbl 0746.90045
[22] T. Homem-de-Mello and G. Bayraksan, {\it Monte Carlo sampling-based methods for stochastic optimization}, Surv. Oper. Res. Manage. Sci., 19 (2014), pp. 56-85.
[23] G. Infanger, {\it Dynamic asset allocation strategies using a stochastic dynamic programming approach}, in Handbook of Asset and Liability Management, S. A. Zenios and W. T. Ziemba, eds., Springer, Berlin, 2006, pp. 200-251.
[24] J. L. Jensen, {\it Sur les fonctions convexes et les inégalités entre les valeurs moyennes}, Acta Math., 30 (1906), pp. 175-193. · JFM 37.0422.02
[25] A. J. Kleywegt, A. Shapiro, and T. Homem-de-Mello, {\it The sample average approximation method for stochastic discrete optimization}, SIAM J. Optim., 12 (2002), pp. 479-502. · Zbl 0991.90090
[26] D. Kuhn, {\it Generalized Bounds for Convex Multistage Stochastic Programs}, Springer, Berlin, 2004. · Zbl 1103.90069
[27] M. Lubin, R. K. Martin, C. Petra, and B. Sand\ikç\i, {\it On parallelizing dual decomposition in stochastic integer programming}, Oper. Res. Lett., 41 (2013), pp. 252-258. · Zbl 1286.90102
[28] G. Lulli and S. Sen, {\it A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems}, Management Sci., 50 (2004), pp. 786-796. · Zbl 1232.90314
[29] A. Madansky, {\it Inequalities for stochastic linear programming problems}, Management Sci., 6 (1960), pp. 197-204. · Zbl 0995.90601
[30] F. Maggioni, E. Allevi, and M. Bertocchi, {\it Bounds in multistage linear stochastic programming}, J. Optim. Theory Appl., 163 (2014), pp. 200-229. · Zbl 1330.90062
[31] F. Maggioni, E. Allevi, and M. Bertocchi, {\it Monotonic bounds in multistage mixed-integer stochastic programming}, Comput. Manage. Sci., (2016), pp. 1-35. · Zbl 1397.90287
[32] F. Maggioni and G. Pflug, {\it Bounds and approximations for multistage stochastic programs}, SIAM J. Optim., 26 (2016), pp. 831-855. · Zbl 1333.90084
[33] W. K. Mak, D. P. Morton, and R. K. Wood, {\it Monte Carlo bounding techniques for determining solution quality in stochastic programs}, Oper. Res. Lett., 24 (1999), pp. 47-56. · Zbl 0956.90022
[34] O. Y. Özalt∈, O. A. Prokopyev, A. J. Schaefer, and M. S. Roberts, {\it Optimizing the societal benefits of the annual influenza vaccine: A stochastic programming approach}, Oper. Res., 59 (2011), pp. 1131-1143. · Zbl 1235.90202
[35] W. B. Powell and H. Topaloglu, {\it Stochastic programming in transportation and logistics}, in Stochastic Programming, Handbooks Oper. Res. Management Sci. 10, A. Ruszczyński and A. Shapiro, eds., Elsevier, Amsterdam, The Netherlands, 2003, pp. 555-635.
[36] W. Römisch and R. Schultz, {\it Multistage stochastic integer programs: An introduction}, in Online Optimization of Large Scale Systems, M. Grötschel, S. O. Krumke, and J. Rambau, eds., Springer, Berlin, 2001, pp. 581-600. · Zbl 1016.90029
[37] D. Ryan, {\it The solution of massive generalized set partitioning problems in aircrew rostering}, J. Oper. Res. Soc., 43 (1992), pp. 459-467.
[38] K. Ryan, S. Ahmed, S. Dey, and D. Rajan, {\it Optimization Driven Scenario Grouping}, Optimization Online, 2016. · Zbl 07290877
[39] B. Sand\ikç\i, N. Kong, and A. J. Schaefer, {\it A hierarchy of bounds for stochastic mixed-integer programs}, Math. Program., 138 (2013), pp. 253-272. · Zbl 1266.90133
[40] B. Sand\ikç\i and Özalt∈, {\it A Scalable Bounding Method for Multi-Stage Stochastic Integer Programs}, Chicago Booth Research Paper 14-21, 2014, .
[41] S. Sen, {\it Algorithms for stochastic mixed-integer programming models}, in Discrete Optimization, Handbooks Oper. Res. Management Sci. 12, G. L. N. K. Aardal and R. Weismantel, eds., Elsevier, Amsterdam, The Netherlands, 2005, pp. 515-558. · Zbl 1172.90457
[42] S. Sen and Z. Zhou, {\it Multistage stochastic decomposition: A bridge between stochastic programming and approximate dynamic programming}, SIAM J. Optim., 24 (2014), pp. 127-153. · Zbl 1291.90153
[43] A. Shapiro, D. Dentcheva, and A. Ruszczyński, {\it Lectures on Stochastic Programming: Modeling and theory}, 2nd ed., SIAM, Philadelphia, PA, 2014. · Zbl 1302.90003
[44] Y. Song and J. Luedtke, {\it An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse}, SIAM J. Optim., 25 (2015), pp. 1344-1367. · Zbl 1317.90222
[45] S. W. Wallace and S. E. Fleten, {\it Stochastic programming models in energy}, in Stochastic Programming, Handbooks in Oper. Res. Management Sci. 10, A. Ruszczyński and A. Shapiro, eds., Elsevier, Amsterdam, The Netherlands, 2003, pp. 637-677.
[46] J. P. Watson and D. L. Woodruff, {\it Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems}, Comput. Management Sci., 8 (2011), pp. 355-370. · Zbl 1225.91032
[47] G. L. Zenarosa, O. A. Prokopyev, and A. J. Schaefer, {\it Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs}, Optimization Online, 2014.
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.