Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design

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
• Angulo G, Ahmed S, Dey SS (2016) Improving the integer L-shaped method. INFORMS J. Comput. 28(3):483–499.Link, Google Scholar
• Batun S, Denton BT, Huschka TR, Schaefer AJ (2011) Operating room pooling and parallel surgery processing under uncertainty. INFORMS J. Comput. 23(2):220–237.Link, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4:238–252.Crossref, Google Scholar
• Bihlmaier R, Koberstein A, Obst R (2009) Modeling and optimizing of strategic and tactical production planning in the automotive industry under uncertainty. OR Spectrum 31:311–336.Crossref, Google Scholar
• Birge JR (1982) The value of the stochastic solution in stochastic linear programs with fixed recourse. Math. Programming 24:314–325.Crossref, Google Scholar
• Birge JR (1985) Aggregation bounds in stochastic linear programming. Math. Programming 31:25–41.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 FV (2011) Introduction to Stochastic Programming (Springer Science and Business Media, New York).Crossref, Google Scholar
• Contreras I, Cordeau J, Laporte G (2011) Benders decomposition for large-scale uncapacitated hub location. Oper. Res. 59(6):1477–1490.Link, 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
• Côté G, Laughton MA (1984) Large-scale mixed integer programs: Benders-type heuristic. Eur. J. Oper. Res. 16(3):327–333.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):73–99.Crossref, Google Scholar
• Crainic TG, 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
• Crainic TG, Hewitt M, Maggioni F, Rei W (2016) Partial Benders decomposition strategies for two-stage stochastic integer programs. Technical Report CIRRELT-2016-37, Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport (CIRRELT), Montreal.Google Scholar
• Crainic TG, Fu X, Gendreau M, Rei W, Wallace SW (2011) Progressive hedging-based metaheuristics for stochastic network design. Networks 58(2):114–124.Crossref, Google Scholar
• de Camargo RS, de Miranda G Jr, Luna HPL (2009) Benders decomposition for hub location problems with economies of scale. Transportation Sci. 43(1):86–97.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. Programming 124:175–182.Crossref, Google Scholar
• Geoffrion AM (1970a) Elements of large-scale mathematical programming part 1: Concepts. Management Sci. 16(11):652–675.Link, Google Scholar
• Geoffrion AM (1970b) Elements of large-scale mathematical programming part 2: Synthesis of algorithms and bibliography. Management Sci. 16(11):676–691.Link, Google Scholar
• Geoffrion AM (1972) Generalized Benders decomposition. J. Optim. Theory Appl. 10(2):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
• Holmberg K (1994) On using approximations of the Benders master problem. Eur. J. Oper. Res. 77(1):111–125.Crossref, Google Scholar
• Hooker JN, Ottosson G (2003) Logic-based Benders decomposition. Math. Programming 96:33–60.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
• Klibi W, Martel A (2012) Scenario-based supply chain network risk modeling. Eur. J. Oper. Res. 223(3):644–658.Crossref, Google Scholar
• Klibi W, Martel A, Guitouni A (2010) The design of robust value-creating supply chain networks: A critical review. Eur. J. Oper. Res. 203(2):283–293.Crossref, Google Scholar
• Litvinchev I, Tsurkov V (2003) Aggregation in Large-Scale Optimization (Kluwer Academic Publishers, Dordrecht, Netherlands).Google Scholar
• Liu Y, Ferris MC, Zhao F (2014) Computational study of security constrained economic dispatch with multi-stage rescheduling. IEEE Trans. Power Systems 30(2):920–929.Crossref, 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
• McDaniel D, Devine M (1977) A modified Benders partitioning algorithm for mixed integer programming. Management Sci. 24(3):312–319.Link, Google Scholar
• MirHassani SA, Lucas C, Mitra G, Messina E, Poojari CA (2000) Computational solution of capacity planning models under uncertainty. Parallel Comput. 26(5):511–538.Crossref, Google Scholar
• Nemhauser G, Wolsey L (1988) Integer and Combinatorial Optimization (Wiley, New York).Crossref, Google Scholar
• Papadakos N (2008) Practical enhancements to the Magnanti-Wong method. Oper. Res. Lett. 36(4):444–449.Crossref, 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
• Pishvaee M, Razmi J, Torabi S (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
• Poojari CA, Beasley JE (2009) Improving Benders decomposition using a genetic algorithm. Eur. J. Oper. Res. 199(1):89–97.Crossref, 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, Ahmed S, Crainic TG, Gendreau M, Rei W (2020) The Benders dual decomposition method. Oper. Res. 68(3):878–895.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
• Rockafellar RT, Uryasev S (2013) The fundamental risk quadrangle in risk management, optimization and statistical estimation. Surveys Oper. Res. Management Sci. 18(1–2):33–53.Crossref, Google Scholar
• Rosa CH, Takriti S (1999) Improving aggregation bounds for two-stage stochastic programs. Oper. Res. Lett. 24(3):127–137.Crossref, Google Scholar
• Roy TJV (1983) Cross decomposition for mixed integer programming. Math. Programming 25(1):46–63.Crossref, Google Scholar
• Sandikçi B, Kong N, Schaefer AJ (2013) A hierarchy of bounds for stochastic mixed-integer programs. Math. Programming 138:253–272.Crossref, Google Scholar
• Shen S, You M, Ma Y (2017) Single-commodity stochastic network design under demand and topological uncertainties with insufficient data. Naval Res. Logist. 64(2):154–173.Crossref, Google Scholar
• Sherali HD, Lunday BJ (2013) On generating maximal nondominated Benders cuts. Ann. Oper. Res. 210: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
• 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 R, Wets RJB (1969) L-shaped programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17(4):638–663.Crossref, Google Scholar
• Wheatley D, Gzara F, Jewkes E (2015) Logic-based Benders decomposition for an inventory-location problem with service constraints. Omega 55:10–23.Crossref, Google Scholar
• Zakeri G, Philpott AD, Ryan DM (2000) Inexact cuts in Benders decomposition. SIAM J. Optim. 10(3):643–657.Crossref, Google Scholar