Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs

References

• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Upper Saddle River, NJ).Google Scholar
• Amaldi E, Capone A, Cesana M, Filippini I, Malucelli F (2008) Optimization models and methods for planning wireless mesh networks. Comput. Networks 52(11):2159–2171.Crossref, Google Scholar
• Barnhart C, Krishnan N, Vance PH (2001) Multicommodity flow problems. Floudas CA, Pardalos PM, eds. Encyclopedia of Optimization (Springer US, Boston), 1583–1591.Crossref, Google Scholar
• Beasley JE (1990) OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41:1069–1072.Crossref, Google Scholar
• Beltran-Royo C (2019) Fast scenario reduction by conditional scenarios in two-stage stochastic MILP problems. Optim. Methods Software 37(1):23–44.Crossref, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1):238–252.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
• Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Program. 98(1):49–71.Crossref, Google Scholar
• Biel M, Johansson M (2020) Dynamic cut aggregation in L-shaped algorithms. Preprint, submitted October 2, https://arxiv.org/abs/1910.13752.Google Scholar
• Birge JR, Louveaux FV (1988) A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34(3):384–392.Crossref, Google Scholar
• Birge JR, Louveaux FV (2011) Introduction to Stochastic Programming, 2nd ed. (Springer Science & Business Media, New York).Crossref, Google Scholar
• Birge JR, Wets RJ-B (1986) Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse. Prékopa A, Wets RJ-B, eds. Stochastic Programming 84 Part 1, Mathematical Programming Studies, vol. 27 (Springer Berlin Heidelberg, Berlin, Heidelberg), 54–102.Crossref, Google Scholar
• Costa AM (2005) A survey on Benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32(6):1429–1450.Crossref, Google Scholar
• Crainic TG, Frangioni A, Gendron B (2001) Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Appl. Math. 112(1–3):73–99.Crossref, Google Scholar
• Crainic TG, Hewitt M, Maggioni F, Rei W (2021) Partial Benders decomposition: General methodology and application to stochastic network design. Transportation Sci. 55(2):414–435.Link, Google Scholar
• Espinoza D, Moreno E (2014) A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs. Comput. Optim. Appl. 59(3):617–638.Crossref, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2016) Benders decomposition without separability: A computational study for capacitated facility location problems. Eur. J. Oper. Res. 253(3):557–569.Crossref, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2017) Redesigning Benders decomposition for large-scale facility location. Management Sci. 63(7):2146–2162.Link, Google Scholar
• Fischetti M, Salvagnin D, Zanette A (2010) A note on the selection of Benders’ cuts. Math. Program. 124(1–2):175–182.Crossref, Google Scholar
• Frauendorfer K (1992) Stochastic Two-Stage Programming, Lecture Notes in Economics and Mathematical Systems, vol. 392 (Springer, Berlin Heidelberg).Crossref, Google Scholar
• Geidl M, Andersson G (2005) A modeling and optimization approach for multiple energy carrier power flow. 2005 IEEE Russia Power Tech (IEEE, Piscataway, NJ), 1–7.Google Scholar
• Gendron B, Crainic TG, Frangioni A (1999) Multicommodity capacitated network design. Sansò B, Soriano P, eds. Telecommunications Network Planning (Springer, Boston), 1–19.Crossref, Google Scholar
• Hewitt M, Ortmann J, Rei W (2022) Decision-based scenario clustering for decision-making under uncertainty. Ann. Oper. Res. 315:747–771.Crossref, Google Scholar
• Huang C, Ziemba WT, Ben-Tal A (1977) Bounds on the expectation of a convex function of a random variable: With applications to stochastic programming. Oper. Res. 25(2):315–325.Link, Google Scholar
• Jin H, Cheocherngngarn T, Levy D, Smith A, Pan D, Liu J, Pissinou N (2013) Joint host-network optimization for energy-efficient data center networking. 2013 IEEE 27th Internat. Sympos. Parallel Distributed Processing (IEEE, Piscataway, NJ), 623–634.Google Scholar
• Keutchayan J, Ortmann J, Rei W (2023) Problem-driven scenario clustering in stochastic optimization. Comput. Management Sci. 20:13. https://doi.org/10.1007/s10287-023-00446-2.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
• Leitner M, Ljubić I, Riedler M, Ruthmair M (2020) Exact approaches for the directed network design problem with relays. Omega 91:102005.Crossref, Google Scholar
• Ljubić I, Mouaci A, Perrot N, Gourdin É (2021) Benders decomposition for a node-capacitated virtual network function placement and routing problem. Comput. Oper. Res. 130:105227.Crossref, Google Scholar
• Louveaux FV (1988) Optimal investments for electricity generation: A stochastic model and a test problem. Ermoliev Y, Wets RJ-B, eds. Numerical Techniques for Stochastic Optimization, Springer Series in Computational Mathematics, vol. 10 (Springer-Verlag, Berlin, Heidelberg).Crossref, Google Scholar
• Mak WK, Morton DP, Wood R (1999) Monte Carlo bounding techniques for determining solution quality in stochastic programs. Oper. Res. Lett. 24(1):47–56.Crossref, Google Scholar
• Pacqueau R, Soumis F, Hoang LN (2012) A fast and accurate algorithm for stochastic integer programming, applied to stochastic shift scheduling. Les Cahiers du GERAD Technical Report G-2012-29, GERAD, HEC Montréal, Montréal.Google Scholar
• Pay BS, Song Y (2020) Partition-based decomposition algorithms for two-stage stochastic integer programs with continuous recourse. Ann. Oper. Res. 284:583–604.Crossref, Google Scholar
• Pierre-Louis P, Bayraksan G, Morton DP (2011) A combined deterministic and sampling-based sequential bounding method for stochastic programming. Proc. 2011 Winter Simulation Conference WSC (IEEE, Piscataway, NJ), 4167–4178.Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Crossref, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2018) Accelerating the Benders decomposition method: Application to stochastic network design problems. SIAM J. Optim. 28(1):875–903.Crossref, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2019) An asynchronous parallel Benders decomposition method. Technical Report CIRRELT-2019-49, Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Université de Montréal, Montréal.Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2021) An asynchronous parallel Benders decomposition method for stochastic network design problems. Technical Report CIRRELT-2021-41, Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et la Transport, Université de Montréal, Montréal.Google Scholar
• Ramirez-Pico C, Moreno E (2022) Generalized adaptive partition-based method for two-stage stochastic linear programs with fixed recourse. Math. Program. 196:755–774.Crossref, Google Scholar
• Rockafellar RT, Uryasev S (2000) Optimization of conditional value-at-risk. J. Risk 2:21–42.Crossref, Google Scholar
• Rubiales AJ, Lotito PA, Parente LA (2013) Stabilization of the generalized Benders decomposition applied to short-term hydrothermal coordination problem. IEEE Latin Amer. Trans. 11(5):1212–1224.Crossref, Google Scholar
• Saharidis GK, Boile M, Theofanis S (2011) Initialization of the Benders master problem using valid inequalities applied to fixed-charge network problems. Expert Systems Appl. 38(6):6627–6636.Crossref, Google Scholar
• Sarayloo F, Crainic TG, Rei W (2021) A learning-based matheuristic for stochastic multicommodity network design. INFORMS J. Comput. 33(2):643–656.Abstract, Google Scholar
• Siddig M, Song Y (2022) Adaptive partition-based SDDP algorithms for multistage stochastic linear programming. Comput. Optim. Appl. 81:201–250.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
• Trukhanov S, Ntaimo L, Schaefer A (2010) Adaptive multicut aggregation for two-stage stochastic linear programs with recourse. Eur. J. Oper. Res. 206(2):395–406.Crossref, Google Scholar
• van Ackooij W, de Oliveira W, Song Y (2018) Adaptive partition-based level decomposition methods for solving two-stage stochastic programs with fixed recourse. INFORMS J. Comput. 30(1):57–70.Link, Google Scholar
• Van Slyke RM, Wets R (1969) L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17(4):638–663.Crossref, Google Scholar
• Vandenbussche B, Delikaraoglou S, Blanco I, Hug G (2019) Data-driven adaptive Benders decomposition for the stochastic unit commitment problem. Preprint, submitted December 2, https://arxiv.org/abs/1912.01039.Google Scholar
• Yang Y, Lee JM (2012) A tighter cut generation strategy for acceleration of Benders decomposition. Comput. Chemical Engrg. 44:84–93.Crossref, Google Scholar
• Zaourar S, Malick J (2014) Quadratic stabilization of Benders decomposition. HAL Technical Report hal-01181273, https://hal.archives-ouvertes.fr/hal-01181273.Google Scholar
• Zäpfel G, Wasner M (2002) Planning and optimization of hub-and-spoke transportation networks of cooperative third-party logistics providers. Internat. J. Production Econom. 78(2):207–220.Crossref, Google Scholar
• Zargham M, Ribeiro A, Ozdaglar A, Jadbabaie A (2013) Accelerated dual descent for network flow optimization. IEEE Trans. Automatic Control 59(4):905–920.Crossref, Google Scholar