Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees

References

• Adulyasak Y, Cordeau JF, Jans R (2015) Benders decomposition for production routing under demand uncertainty. Oper. Res. 63(4):851–867.Link, Google Scholar
• Ahmed S (2013) A scenario decomposition algorithm for 0–1 stochastic programs. Oper. Res. Lett. 41(6):565–569.Crossref, Google Scholar
• Ahmed S, Luedtke J, Song Y, Xie W (2017) Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs. Math. Programming 162(1–2):51–81.Crossref, Google Scholar
• Arpón S, Homem-de Mello T, Pagnoncelli B (2018) Scenario reduction for stochastic programs with conditional value-at-risk. Math. Programming 170(1):327–356.Crossref, Google Scholar
• Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52(5):723–738.Link, Google Scholar
• Bertsimas D, Kallus N (2020) From predictive to prescriptive analytics. Management Sci. 66(3):1025–1044.Link, Google Scholar
• Bertsimas D, King A, Mazumder R (2016) Best subset selection via a modern optimization lens. Ann. Statist. 44(2):813–852.Crossref, Google Scholar
• Bertsimas D, Mundru N (2022) Optimization-based scenario reduction for data-driven two-stage stochastic optimization. Oper. Res., ePub ahead of print April 4, https://doi.org/10.1287/opre.2022.2265.Link, Google Scholar
• Birge J, Louveaux F (2011) Introduction to Stochastic Programming (Springer, New York).Crossref, Google Scholar
• Carøe CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1–2):37–45.Crossref, Google Scholar
• Casey MS, Sen S (2005) The scenario generation algorithm for multistage stochastic linear programming. Math. Oper. Res. 30(3):615–631.Link, Google Scholar
• Crainic T, Hewitt M, Rei W (2014) Scenario grouping in a progressive hedging-based meta-heuristic for stochastic network design. Comput. Oper. Res. 43:90–99.Crossref, Google Scholar
• Dantzig GB, Madansky A (1961) On the solution of two-stage linear programs under uncertainty. Proc. Fourth Berkeley Sympos. Math. Statist. Probab., vol. 1 (University of California Press, Berkeley, CA).Google Scholar
• Dempster MAH (2006) Sequential importance sampling algorithms for dynamic stochastic programming. J. Math. Sci. 133(4):1422–1444.Crossref, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2006) Column Generation (Springer, New York).Google Scholar
• Drew SS, Homem-de-Mello T (2006) Quasi-Monte Carlo strategies for stochastic optimization. Proc. 2006 Winter Simulation Conf. (IEEE, Piscataway, NJ), 774–782.Google Scholar
• Dupačová J, Gröwe-Kuska N, Römisch W (2003) Scenario reduction in stochastic programming. Math. Programming 95(3):493–511.Crossref, Google Scholar
• Fairbrother J, Turner A, Wallace SW (2018) Scenario generation for single-period portfolio selection problems with tail risk measures: Coping with high dimensions and integer variables. INFORMS J. Comput. 30(3):472–491.Link, Google Scholar
• Fairbrother J, Turner A, Wallace SW (2019) Problem-driven scenario generation: An analytical approach for stochastic programs with tail risk measure. Math. Programming 191:141–182.Crossref, Google Scholar
• Feng Y, Ryan SM (2016) Solution sensitivity-based scenario reduction for stochastic unit commitment. Comput. Management Sci. 13(1):29–62.Crossref, Google Scholar
• Gade D, Hackebeil G, Ryan S, Watson JP, Wets R, Woodruff D (2016) Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs. Math. Programming 157(1):47–67.Crossref, Google Scholar
• Guo C, Bodur M, Aleman DM, Urbach DR (2021) Logic-based benders decomposition and binary decision diagram based approaches for stochastic distributed operating room scheduling. INFORMS J. Comput. 33(4):1551–1569.Abstract, Google Scholar
• Heitsch H, Römisch W (2007) A note on scenario reduction for two-stage stochastic programs. Oper. Res. Lett. 35(6):731–738.Crossref, Google Scholar
• Henrion R, Römisch W (2018) Problem-based optimal scenario generation and reduction in stochastic programming. Math. Programming 191:183–205.Crossref, Google Scholar
• Higle JL (1998) Variance reduction and objective function evaluation in stochastic linear programs. INFORMS J. Comput. 10(2):236–247.Link, Google Scholar
• Hochreiter R, Pflug GC (2007) Financial scenario generation for stochastic multi-stage decision processes as facility location problems. Ann. Oper. Res. 152(1):257–272.Crossref, Google Scholar
• Homem-de-Mello T (2008) On rates of convergence for stochastic optimization problems under non–independent and identically distributed sampling. SIAM J. Optim. 19(2):524–551.Crossref, Google Scholar
• Høyland K, Kaut M, Wallace SW (2003) A heuristic for moment-matching scenario generation. Comput. Optim. Appl. 24(2–3):169–185.Crossref, Google Scholar
• Høyland K, Wallace SW (2001) Generating scenario trees for multistage decision problems. Management Sci. 47(2):295–307.Link, Google Scholar
• Khassiba A, Bastin F, Cafieri S, Gendron B, Mongeau M (2020) Two-stage stochastic mixed-integer programming with chance constraints for extended aircraft arrival management. Transportation Sci. 54(4):897–919.Link, Google Scholar
• King A, Wallace SW (2012) Modeling with Stochastic Programming (Springer, New York).Crossref, Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de-Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Koivu M (2005) Variance reduction in sample approximations of stochastic programs. Math. Programming 103(3):463–485.Crossref, Google Scholar
• Laporte G, Louveaux FV (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. 13(3):133–142.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Luedtke J (2016) Tutorial: Stochastic integer programming. XIV Internat. Conf. Stochastic Programming, University of Madison, Madison, WI.Google Scholar
• Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Mak WK, Morton DP, Wood RK (1999) Monte Carlo bounding techniques for determining solution quality in stochastic programs. Oper. Res. Lett. 24(1–2):47–56.Crossref, Google Scholar
• Narum BS (2020) Problem-based scenario generation in stochastic programming with binary distributions: Case study in air traffic flow management. Unpublished master’s thesis, Norwegian University of Science and Technology, Trondheim, Norway.Google Scholar
• Nemirovski A, Shapiro A (2006) Scenario approximations of chance constraints. Calafiore G, Dabbene F, eds. Probabilistic and Randomized Methods for Design Under Uncertainty (Springer, London), 3–47.Crossref, Google Scholar
• Park J, Stockbridge R, Bayraksan G (2021) Variance reduction for sequential sampling in stochastic programming. Ann. Oper. Res. 300(1):171–204.Crossref, Google Scholar
• Parpas P, Ustun B, Webster M, Tran QK (2015) Importance sampling in stochastic programming: A Markov chain Monte Carlo approach. INFORMS J. Comput. 27(2):358–377.Link, Google Scholar
• Penuel J, Smith JC, Yuan Y (2010) An integer decomposition algorithm for solving a two-stage facility location problem with second-stage activation costs. Naval Res. Logist. 57(5):391–402.Crossref, Google Scholar
• Pflug GC (2001) Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Programming 89(2):251–271.Crossref, Google Scholar
• Prochazka V, Wallace SW (2018) Stochastic programs with binary distributions: Structural properties of scenario trees and algorithms. Comput. Management Sci. 15(3–4):397–410.Crossref, Google Scholar
• Prochazka V, Wallace SW (2020) Scenario tree construction driven by heuristic solutions of the optimization problem. Comput. Management Sci. 17:277–307.Crossref, Google Scholar
• Ralph D, Xu H (2011) Convergence of stationary points of sample average two-stage stochastic programs: A generalized equation approach. Math. Oper. Res. 36(3):568–592.Link, Google Scholar
• Rockafellar T, Wets R (1991) Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1):119–147.Link, Google Scholar
• Römisch W (2009) Scenario reduction techniques in stochastic programming. Watanabe O, Zeugmann T, eds. Stochastic Algorithms: Foundations and Applications (Springer, Berlin), 1–14.Crossref, Google Scholar
• Ryan K, Ahmed S, Dey SS, Rajan D, Musselman A, Watson JP (2020) Optimization-driven scenario grouping. INFORMS J. Comput. 32(3):805–821.Link, Google Scholar
• Schütz P, Tomasgard A, Ahmed S (2009) Supply chain design under uncertainty using sample average approximation and dual decomposition. Eur. J. Oper. Res. 199(2):409–419.Crossref, Google Scholar
• Seljom P, Tomasgard A (2021) Sample average approximation and stability tests applied to energy system design. Energy Systems 12(1):107–131.Crossref, Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2014) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Crossref, Google Scholar
• Shapiro A, Homem-de-Mello T (2000) On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs. SIAM J. Optim. 11(1):70–86.Crossref, Google Scholar
• Shapiro A, Xu H (2008) Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation. Optim. 57(3):395–418.Crossref, Google Scholar
• Sherali HD, Lunday BJ (2013) On generating maximal nondominated Benders cuts. Ann. Oper. Res. 210(1):57–72.Crossref, Google Scholar
• Song Y, Luedtke J (2015) An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse. SIAM J. Optim. 25(3):1344–1367.Crossref, Google Scholar
• Sun M, Teng F, Konstantelos I, Strbac G (2018) An objective-based scenario selection method for transmission network expansion planning with multivariate stochasticity in load and renewable energy sources. Energy 145:871–885.Crossref, Google Scholar
• Van Parys BP, Esfahani PM, Kuhn D (2021) From data to decisions: Distributionally robust optimization is optimal. Management Sci. 67(6):3387–3402.Link, Google Scholar
• Wang K, Jacquillat A (2020) A stochastic integer programming approach to air traffic scheduling and operations. Oper. Res. 68(5):1375–1402.Link, Google Scholar
• Yoon S, Albert LA, White VM (2021) A stochastic programming approach for locating and dispatching two types of ambulances. Transportation Sci. 55(2):275–296.Link, Google Scholar
• Zhou L, Geng N, Jiang Z, Jiang S (2022) Integrated multiresource capacity planning and multitype patient scheduling. INFORMS J. Comput. 34(1):129–149.Link, Google Scholar