A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm

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
• Atamtürk A, Nemhauser GL, Savelsbergh MW (2001) Valid inequalities for problems with additive variable upper bounds. Math. Programming 91(1):145–162.Crossref, Google Scholar
• Balinski ML (1965) Integer programming: Methods, uses, computations. Management Sci. 12(3):253–313.Link, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Math. 4(1):238–252.Crossref, Google Scholar
• Bertsekas DP (1999) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• Brandenberg R, Stursberg P (2021) Refined cut selection for Benders decomposition: Applied to network capacity expansion problems. Math. Method Oper. Res. 94(3):383–412.Google Scholar
• Codato G, Fischetti M (2006) Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4):756–766.Link, Google Scholar
• Conforti M, Wolsey LA (2019) “Facet” separation with one linear program. Math. Programming 178(1–2):361–380.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
• Dinkelbach W (1967) On nonlinear fractional programming. Management Sci. 13(7):492–498.Link, Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2016) 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(1–2):175–182.Crossref, Google Scholar
• Fukuda K, Prodon A (2005) Double description method revisited. Deza M, Euler R, Manoussakis I, eds. Combinatorics and Computer Science. Lecture Notes in Computer Science 1120 (Springer, Berlin, Heidelberg), 91–111.Google Scholar
• Fukuda K, Liebling TM, Margot F (1997) Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. Comput. Geometry 8(1):1–12.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
• Hooker JN (2007) Planning and scheduling by logic-based Benders decomposition. Oper. Res. 55(3):588–602.Link, Google Scholar
• Hooker J, Ottosson G (2003) Logic-based Benders decomposition. Math. Programming 96(1):33–60.Crossref, Google Scholar
• Hosseini M, Turner J (2021) Deepest cuts for Benders decomposition. Preprint, submitted October 16, https://arxiv.org/abs/2110.08448.Google Scholar
• Kewcharoenwong P, Üster H (2014) Benders decomposition algorithms for the fixed-charge relay network design in telecommunications. Telecomm. Systems 56(4):441–453.Crossref, Google Scholar
• Lai MC, Sohn HS, Tseng TLB, Chiang C (2010) A hybrid algorithm for capacitated plant location problem. Expert Systems Appl. 37(12):8599–8605.Crossref, Google Scholar
• Lee C, Lee K, Park S (2013) Benders decomposition approach for the robust network design problem with flow bifurcations. Networks 62(1):1–16.Crossref, Google Scholar
• Lin H, Üster H (2014) Exact and heuristic algorithms for data-gathering cluster-based wireless sensor network design problem. IEEE/ACM Trans. Networking 22(3):903–916.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
• 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
• Orlowski S, Pióro M, Tomaszewski A, Wessäly R (2010) SNDlib 1.0–Survivable network design library. Networks 55(3):276–286.Google Scholar
• Papadakos N (2008) Practical enhancements to the Magnanti–Wong method. Oper. Res. Lett. 36(4):444–449.Crossref, Google Scholar
• Porumbel D (2018) From the separation to the intersection sub-problem in Benders decomposition models with prohibitively-many constraints. Discrete Optim. 29:148–173.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
• 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
• 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
• Watson FR, Rogers DF (2007) Pareto-optimality of the Balinski cut for the uncapacitated facility location problem. Internat. J. Oper. Res. 4(3):155–164.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