A Stochastic Benders Decomposition Scheme for Large-Scale Stochastic Network Design

References

• Agrawal A, Klein P, Ravi R (1991) When trees collide: An approximation algorithm for the generalized Steiner problem on networks. Koutsougeras S, Vitter J, eds. STOC ’91: Proc. Twenty-Third Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 134–144.Google Scholar
• Atamtürk A, Günlük O (2018) A note on capacity models for network design. Oper. Res. Lett. 46(4):414–417.Crossref, Google Scholar
• Atamtürk A, Günlük O (2021) Multicommodity multifacility network design. Crainic TG, Gendreau M, Gendron B, eds. Network Design with Applications to Transportation and Logistics (Springer, Cham, Switzerland), 141–166.Crossref, Google Scholar
• Balakrishnan A, Magnanti TL, Shulman A, Wong RT (1991) Models for planning capacity expansion in local access telecommunication networks. Ann. Oper. Res. 33(4):237–284.Crossref, Google Scholar
• Barnhart C, Belobaba P, Odoni AR (2003) Applications of operations research in the air transport industry. Transportation Sci. 37(4):368–391.Link, Google Scholar
• Bayraksan G, Morton DP (2011) A sequential sampling procedure for stochastic programming. Oper. Res. 59(4):898–913.Link, Google Scholar
• Beale EM (1955) On minimizing a convex function subject to linear inequalities. J. Roy. Statist. Soc. B Methodological 17(2):173–184.Crossref, Google Scholar
• Bertsimas D, Li ML (2022) Stochastic cutting planes for data-driven optimization. INFORMS J. Comput. 34(5):2400–2409.Link, Google Scholar
• Bertsimas D, Teo CP (1998) From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems. Oper. Res. 46(4):503–514.Link, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization, vol. 6 (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D, Cory-Wright R, Pauphilet J (2021) A unified approach to mixed-integer optimization problems with logical constraints. SIAM J. Optim. 31(3):2340–2367.Crossref, Google Scholar
• Bertsimas D, Cory-Wright R, Pauphilet J, Petridis P (2024) A stochastic Benders decomposition scheme for large-scale stochastic network design. http://dx.doi.org/10.1287/ijoc.2023.0074.cd, https://github.com/INFORMSJoC/2023.0074.Google Scholar
• Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65–98.Crossref, Google Scholar
• Bienstock D, Chopra S, Günlük O, Tsai CY (1998) Minimum cost capacity installation for multicommodity network flows. Math. Programming 81(2):177–199.Crossref, Google Scholar
• Binato S, Pereira MVF, Granville S (2001) A new Benders decomposition approach to solve power transmission network design problems. IEEE Trans. Power Systems 16(2):235–240.Crossref, 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 F (2011) Introduction to Stochastic Programming, Springer Series in Operations Research and Financial Engineering (Springer, New York).Crossref, Google Scholar
• Bixby RE (2012) A brief history of linear and mixed-integer programming computation. Documenta Math. 2012:107–121.Google Scholar
• Boyce DE, Farhi A, Weischedel R (1973) Optimal network problem: A branch-and-bound algorithm. Environ. Planning A Econom. Space 5(4):519–533.Crossref, Google Scholar
• Ceria S, Soares J (1999) Convex programming for disjunctive convex optimization. Math. Programming 86(3):595–614.Crossref, Google Scholar
• Contreras I, Cordeau JF, Laporte G (2011) Benders decomposition for large-scale uncapacitated hub location. Oper. Res. 59(6):1477–1490.Link, Google Scholar
• Cornuejols G, Nemhauser GL, Wolsey LA (1980) A canonical representation of simple plant location problems and its applications. SIAM J. Algebraic Discrete Methods 1(3):261–272.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, Gendreau M, Farvolden JM (2000) A simplex-based Tabu search method for capacitated network design. INFORMS J. Comput. 12(3):223–236.Link, Google Scholar
• Crainic TG, Gendreau M, Gendron B, eds. (2021a) Network Design with Applications to Transportation and Logistics (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• Crainic TG, Hewitt M, Maggioni F, Rei W (2021b) Partial Benders decomposition: General methodology and application to stochastic network design. Transportation Sci. 55(2):414–435.Link, Google Scholar
• Crainic TG, Rei W, Hewitt M, Maggioni F (2016) Partial Benders decomposition strategies for two-stage stochastic integer programs. Report No. CIRRELT-2016-37, CIRRELT, Montreal.Google Scholar
• Dantzig GB (1955) Linear programming under uncertainty. Management Sci. 1(3–4):197–206.Link, Google Scholar
• Dantzig GB, Infanger G (1993) Multi-stage stochastic linear programs for portfolio optimization. Ann. Oper. Res. 45(1):59–76.Crossref, Google Scholar
• Davis D, Drusvyatskiy D, Kakade S, Lee JD (2020) Stochastic subgradient method converges on tame functions. Foundations Comput. Math. 20(1):119–154.Crossref, Google Scholar
• de Camargo RS, Miranda G Jr, Luna HP (2008) Benders decomposition for the uncapacitated multiple allocation hub location problem. Comput. Oper. Res. 35(4):1047–1064.Crossref, Google Scholar
• De Matos VL, Philpott AB, Finardi EC (2015) Improving the performance of stochastic dual dynamic programming. J. Comput. Appl. Math. 290:196–208.Crossref, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• Erickson RE, Monma CL, Veinott AF Jr (1987) Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12(4):634–664.Link, Google Scholar
• Fábián CI (2000) Bundle-type methods for inexact data. CEJOR Central Eur. J. Oper. Res. 8(1):35–55.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
• Florian M, Bushell G, Ferland J, Guerin G, Nastansky L (1976) The engine scheduling problem in a railway network. INFOR Inform. Systems Oper. Res. 14(2):121–138.Crossref, Google Scholar
• Garey MR, Johnson DS (1977) The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4):826–834.Crossref, Google Scholar
• Gendron B, Crainic TG, Frangioni A (1999) Multicommodity capacitated network design. Sansò B, Soriano P, eds. Telecommunications Network Planning, Centre for Research on Transportation (Springer, Boston), 1–19.Crossref, Google Scholar
• Gendron B, Hanafi S, Todosijević R (2018) Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design. Eur. J. Oper. Res. 268(1):70–81.Crossref, Google Scholar
• Geoffrion AM (1972) Generalized Benders decomposition. J. Optim. Theory Appl. 10(4):237–260.Crossref, Google Scholar
• Geoffrion AM, Graves GW (1974) Multicommodity distribution system design by Benders decomposition. Management Sci. 20(5):822–844.Link, Google Scholar
• Glover F (1975) Improved linear integer programming formulations of nonlinear integer problems. Management Sci. 22(4):455–460.Link, Google Scholar
• Goemans MX, Bertsimas DJ (1993) Survivable networks, linear programming relaxations and the parsimonious property. Math. Programming 60(1):145–166.Crossref, Google Scholar
• Grimmett G, Stirzaker D (2020) Probability and Random Processes (Oxford University Press, Oxford, UK).Google Scholar
• Guigues V (2020) Inexact cuts in stochastic dual dynamic programming. SIAM J. Optim. 30(1):407–438.Crossref, Google Scholar
• Günlük O (1999) A branch-and-cut algorithm for capacitated network design problems. Math. Programming 86(1):17–39.Crossref, Google Scholar
• Günlük O, Linderoth J (2009) Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Programming 124:183–205.Crossref, Google Scholar
• Gurobi Optimization LLC (2022) Gurobi Optimizer reference manual. Accessed April 2024, https://www.gurobi.com/documentation/current/refman/index.html.Google Scholar
• Higle JL, Sen S (1991) Stochastic decomposition: An algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16(3):650–669.Link, Google Scholar
• Higle JL, Sen S (1996) Duality and statistical tests of optimality for two stage stochastic programs. Math. Programming 75(2):257–275.Crossref, Google Scholar
• Infanger G (1992) Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39(1):69–95.Crossref, Google Scholar
• Ke Q, Ferrara E, Radicchi F, Flammini A (2015) Defining and identifying sleeping beauties in science. Proc. Natl. Acad. Sci. USA 112(24):7426–7431.Crossref, Google Scholar
• Kingma DP, Ba J (2014) Adam: A method for stochastic optimization. Preprint, submitted December 22, https://arxiv.org/abs/1412.6980.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
• Magnanti TL, Wong RT (1984) Network design and transportation planning: Models and algorithms. Transportation Sci. 18(1):1–55.Link, Google Scholar
• Magnanti TL, Mirchandani P, Vachani R (1993) The convex hull of two core capacitated network design problems. Math. Programming 60(1):233–250.Crossref, Google Scholar
• Magnanti TL, Mirchandani P, Vachani R (1995) Modeling and solving the two-facility capacitated network loading problem. Oper. Res. 43(1):142–157.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
• McDaniel D, Devine M (1977) A modified Benders’ partitioning algorithm for mixed integer programming. Management Sci. 24(3):312–319.Link, Google Scholar
• Morton DP (1998) Stopping rules for a class of sampling-based stochastic programming algorithms. Oper. Res. 46(5):710–718.Link, Google Scholar
• Papadakos N (2008) Practical enhancements to the Magnanti–Wong method. Oper. Res. Lett. 36(4):444–449.Crossref, Google Scholar
• Pereira MV, Pinto LM (1991) Multi-stage stochastic optimization applied to energy planning. Math. Programming 52(1):359–375.Crossref, Google Scholar
• Pishvaee MS, Razmi J, Torabi SA (2014) An accelerated Benders decomposition algorithm for sustainable supply chain network design under uncertainty: A case study of medical needle and syringe supply chain. Transportation Res. Part E Logist. Transportation Rev. 67:14–38.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
• Ramírez-Pico C, Ljubić I, Moreno E (2023) Benders adaptive-cuts method for two-stage stochastic programs. Transportation Sci. 57(5):1252–1275.Link, Google Scholar
• Rei W, Cordeau JF, Gendreau M, Soriano P (2009) Accelerating Benders decomposition by local branching. INFORMS J. Comput. 21(2):333–345.Link, Google Scholar
• Reuther A, Kepner J, Byun C, Samsi S, Arcand W, Bestor D, Bergeron B, et al. (2018) Interactive supercomputing on 40,000 cores for machine learning and data analysis. 2018 IEEE High Performance Extreme Comput. Conf. (HPEC) (Curran Associates, Red Hook, NY), 1–6.Google Scholar
• Richardson R (1976) An optimization approach to routing aircraft. Transportation Sci. 10(1):52–71.Link, Google Scholar
• Rodríguez-Martín I, Salazar-González JJ (2010) A local branching heuristic for the capacitated fixed-charge network design problem. Comput. Oper. Res. 37(3):575–581.Crossref, Google Scholar
• Santoso T, Ahmed S, Goetschalckx M, Shapiro A (2005) A stochastic programming approach for supply chain network design under uncertainty. Eur. J. Oper. Res. 167(1):96–115.Crossref, Google Scholar
• Schmidt M, Le Roux N, Bach F (2017) Minimizing finite sums with the stochastic average gradient. Math. Programming 162(1):83–112.Crossref, Google Scholar
• Shapiro A, Dentcheva D, Ruszczynski A (2021) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Crossref, Google Scholar
• Smith JE, Winkler RL (2006) The optimizer’s curse: Skepticism and postdecision surprise in decision analysis. Management Sci. 52(3):311–322.Link, Google Scholar
• Stubbs RA, Mehrotra S (1999) A branch-and-cut method for 0-1 mixed convex programming. Math. Programming 86(3):515–532.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 Roy TJ, Wolsey LA (1985) Valid inequalities and separation for uncapacitated fixed charge networks. Oper. Res. Lett. 4(3):105–112.Crossref, 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
• Wei L, Gómez A, Küçükyavuz S (2022) Ideal formulations for constrained convex optimization problems with indicator variables. Math. Programming 192(1):57–88.Crossref, Google Scholar
• Wets RJB (1966) Programming under uncertainty: The equivalent convex program. SIAM J. Appl. Math. 14(1):89–105.Crossref, Google Scholar
• Xie W, Deng X (2020) Scalable algorithms for the sparse ridge regression. SIAM J. Optim. 30(4):3359–3386.Crossref, Google Scholar
• You F, Grossmann IE (2013) Multicut Benders decomposition algorithm for process supply chain planning under uncertainty. Ann. Oper. Res. 210(1):191–211.Crossref, Google Scholar
• Zakeri G, Philpott AB, Ryan DM (2000) Inexact cuts in Benders decomposition. SIAM J. Optim. 10(3):643–657.Crossref, Google Scholar