The Benders Dual Decomposition Method

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
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1):238–252.Crossref, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• Bodur M, Dash S, Günlük O, Luedtke J (2017) Strengthened Benders cuts for stochastic integer programs with continuous recourse. INFORMS J. Comput. 29(1):77–91.Link, Google Scholar
• Boland N, Fischetti M, Monaci M, Savelsbergh M (2016) Proximity Benders: A decomposition heuristic for stochastic programs. J. Heuristics 22(2):181–198.Crossref, Google Scholar
• Carøe CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1):37–45.Google Scholar
• Cerisola S, Baíllo Á, Fernández-López JM, Ramos A, Gollmer R (2009) Stochastic power generation unit commitment in electricity markets: A novel formulation and a comparison of solution methods. Oper. Res. 57(1):32–46.Link, Google Scholar
• Codato G, Fischetti M (2006) Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4):756–766.Link, 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
• Cordeau JF, Pasin F, Solomon MM (2006) An integrated model for logistics network design. Ann. Oper. Res. 144(1):59–82.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):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, Rei W (2016) Partial Benders decomposition strategies for two-stage stochastic integer programs. Publication CIRRELT-2016-37, Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport, Université de Montréal, Montréal.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
• 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, Salvagnin D, Zanette A (2010) A note on the selection of Benders’ cuts. Math. Programming 124(1):175–182.Crossref, Google Scholar
• Flippo OE, Rinnooy Kan AHG (1993) Decomposition in general mathematical programming. Math. Programming 60(1):361–382.Crossref, Google Scholar
• Fragkogios A, Saharidis GK (2018) Latest advances on Benders decomposition. Encyclopedia of Information Science and Technology, 4th ed. (IGI Global, Hershey, PA), 5411–5421.Crossref, Google Scholar
• Gendron B, Scutellà MG, Garroppo RG, Nencioni G, Tavanti L (2016) A Branch-and-Benders-cut method for nonlinear power design in green wireless local area networks. Eur. J. Oper. Res. 255(1):151–162.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
• Grothey A, Leyffer S, McKinnon K (1999) A note on feasibility in Benders decomposition. Numerical Analysis Report NA/188, Dundee University, Nethergate, Dundee, UK.Google Scholar
• Holmberg K (1990) On the convergence of cross decomposition. Math. Programming 47(1):269–296.Crossref, Google Scholar
• Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA (2009) 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art (Springer Science & Business Media, New York).Google Scholar
• Lin S, Lim GJ, Bard JF (2016) Benders decomposition and an IP-based heuristic for selecting IMRT treatment beam angles. Eur. J. Oper. Res. 251(3):715–726.Crossref, Google Scholar
• Louveaux FV (1986) Discrete stochastic location models. Ann. Oper. Res. 6(2):21–34.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
• Mitra S, Garcia-Herreros P, Grossmann IE (2016) A cross-decomposition scheme with integrated primal–dual multi-cuts for two-stage stochastic programming investment planning problems. Math. Programming 157(1):95–119.Crossref, Google Scholar
• Naoum-Sawaya J, Elhedhli S (2013) An interior-point benders based branch-and-cut algorithm for mixed integer programs. Ann. Oper. Res. 210(1):33–55.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (Wiley-Interscience, New York).Crossref, Google Scholar
• Newman AM, Weiss M (2013) A survey of linear and mixed-integer optimization tutorials. INFORMS Trans. Ed. 14(1):26–38.Link, Google Scholar
• Pacqueau R, Francois S, Le Nguyen H (2012) A fast and accurate algorithm for stochastic integer programming, appllied to stochastic shift scheduling. Publication G-2012-29, Groupe d’études et de recherche en analyse des décisions (GERAD), Université de Montréal, Montréal.Google Scholar
• Pan F, Morton DP (2008) Minimizing a stochastic maximum-reliability path. Networks 52(3):111–119.Crossref, Google Scholar
• Papadakos N (2008) Practical enhancements to the magnanti–wong method. Oper. Res. Lett. 36(4):444–449.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 (2017a) A Benders decomposition method for two-stage stochastic network design problems. Publication CIRRELT-2017-22, 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 (2017b) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Crossref, 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, Wets RJB (1991) Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1):119–147.Link, Google Scholar
• Rush AM, Collins M (2012) A tutorial on dual decomposition and lagrangian relaxation for inference in natural language processing. J. Artificial Intelligence Res. 45(1):305–362.Crossref, Google Scholar
• Ruszczyński A (1997) Decomposition methods in stochastic programming. Math. Programming 79(1):333–353.Crossref, Google Scholar
• Sahinidis N, Grossmann I (1991) Convergence properties of generalized Benders decomposition. Comput. Chemical Engrg. 15(7):481–491.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
• Sherali HD, Lunday BJ (2013) On generating maximal nondominated Benders cuts. Ann. Oper. Res. 210(1):57–72.Crossref, Google Scholar
• Van Roy TJ (1983) Cross decomposition for mixed integer programming. Math. Programming 25(1):46–63.Crossref, Google Scholar
• Zou J, Ahmed S, Sun XA (2018) Stochastic dual dynamic integer programming. Math. Programming 175(1):461–502.Google Scholar