A Tailored Branch-and-Benders-Cut Approach for Backup Covering Problems

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
• Armacost RL (1992) A 0-1 nonlinear programming model for coast guard fisheries law enforcement aircraft patrols. Eur. J. Oper. Res. 56(2):134–145.Crossref, Google Scholar
• Ben-Ameur W, Neto J (2007) Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks 49(1):3–17.Crossref, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1):238–252.Crossref, Google Scholar
• Bonami P, Salvagnin D, Tramontani A (2020) Implementing automatic benders decomposition in a modern MIP solver. Bienstock D, Zambelli G, eds. Integer Programming Combin. Optim. IPCO 2020, Lecture Notes in Computer Science, vol. 12125 (Springer, Cham, Switzerland), 78–90.Google Scholar
• Brotcorne L, Laporte G, Semet F (2003) Ambulance location and relocation models. Eur. J. Oper. Res. 147(3):451–463.Crossref, Google Scholar
• Chowdhury N, Pilo F, Pisano G (2020) Optimal energy storage system positioning and sizing with robust optimization. Energies 13(3):512.Crossref, Google Scholar
• Church RL, ReVelle CS (1974) The maximal covering location problem. Papers Regional Sci. Assoc. 32:101–118.Crossref, Google Scholar
• Clautiaux F, Ljubić I (2025) Last fifty years of integer linear programming: A focus on recent practical advances. Eur. J. Oper. Res. 324(3):707–731.Crossref, Google Scholar
• Codato G, Fischetti M (2006) Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4):756–766.Link, Google Scholar
• Coniglio S, Furini F, Ljubić I (2022) Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems. Math. Programming 196(1):9–56.Crossref, Google Scholar
• Cordeau JF, Furini F, Ljubić I (2019) Benders decomposition for very large scale partial set covering and maximal covering location problems. Eur. J. Oper. Res. 275(3):882–896.Crossref, Google Scholar
• Current J, O’Kelly M (1992) Locating emergency warning sirens. Decision Sci. 23(1):221–234.Crossref, Google Scholar
• Daskin MS (1983) A maximum expected covering location model: Formulation, properties and heuristic solution. Transportation Sci. 17(1):48–70.Link, Google Scholar
• Daskin MS, Stern EH (1981) A hierarchical objective set covering model for emergency medical service vehicle deployment. Transportation Sci. 15(2):137–152.Link, Google Scholar
• Doerner K, Hartl R (2008) Health care logistics, emergency preparedness, and disaster relief: New challenges for routing problems with a focus on the Austrian situation. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges, Operations Research/Computer Science Interfaces, vol. 43 (Springer, Boston, MA), 527–550.Crossref, Google Scholar
• Doerner KF, Gutjahr WJ, Hartl RF, Karall M, Reimann M (2005) Heuristic solution of an extended double-coverage ambulance location problem for Austria. Central Eur. J. Oper. Res. 13(4):325–340.Google Scholar
• Duran-Mateluna C, Ales Z, Elloumi S (2023) An efficient Benders decomposition for the p-median problem. Eur. J. Oper. Res. 308(1):84–96.Crossref, Google Scholar
• Fadda E, Ljubić I, Manerba D (2026) A tailored branch-and-Benders-cut approach for backup covering problems. https://doi.org/10.1287/ijoc.2025.1394.cd, https://github.com/INFORMSJoC/2025.1394.Google Scholar
• Fadda E, Manerba D, Tadei R (2024) How to locate services optimizing redundancy: A comparative analysis of k-covering facility location models. Socio-econom. Planning Sci. 94:101938.Crossref, Google Scholar
• Fadda E, Manerba D, Cabodi G, Camurati P, Tadei R (2021a) Evaluation of optimal charging station location for electric vehicles: An Italian case-study. Fidanova S, ed. Recent Advances in Computational Optimization, Springer Studies in Computational Intelligence, vol. 920 (Springer, Cham, Switzerland), 71–87.Crossref, Google Scholar
• Fadda E, Manerba D, Cabodi G, Camurati PE, Tadei R (2021b) Comparative analysis of models and performance indicators for optimal service facility location. Transportation Res. Part E Logist. Transportation Rev. 145:102174.Crossref, Google Scholar
• Fadda E, Manerba D, Tadei R, Camurati P, Cabodi G, Ganzha M, Maciaszek L, Paprzycki M (2019) KPIs for optimal location of charging stations for electric vehicles: The Biella case-study. Ganzha M, Maciaszek L, Paprzycki M, eds. Proc. 2019 Federated Conf. Comput. Sci. Inform. Systems, vol. 18 (Polish Information Processing Society, Warsaw), 123–126.Google Scholar
• Farahani RZ, Asgari N, Heidari N, Hosseininia M, Goh M (2012) Covering problems in facility location: A review. Comput. Indust. Engrg. 62(1):368–407.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
• Gaar E, Sinnl M (2022) A scaleable projection‐based branch‐and‐cut algorithm for the p‐center problem. Eur. J. Oper. Res. 303(1):78–98.Crossref, Google Scholar
• García S, Marín A (2019) Covering location problems. Laporte G, Nickel S, Saldanha da Gama F, eds. Location Science (Springer, Cham, Switzerland), 99–119.Crossref, Google Scholar
• Gendreau M, Laporte G, Semet F (1997) Solving an ambulance location model by tabu search. Location Sci. 5(2):75–88.Crossref, Google Scholar
• Hogan K, ReVelle C (1986) Concepts and applications of backup coverage. Management Sci. 32(11):1434–1444.Link, Google Scholar
• IBM ILOG CPLEX Optimization Studio (2022) Linear reduction switch. Accessed April 19, 2026, https://www.ibm.com/docs/en/icos/22.1.0?topic=parameters-linear-reduction-switch-deprecated.Google Scholar
• Kahr M, Leitner M, Ljubić I (2024) The impact of passive social media viewers in influence maximization. INFORMS J. Comput. 36(6):1362–1381.Link, Google Scholar
• Lamontagne S, Carvalho M, Atallah R (2024) Accelerated Benders decomposition and local branching for dynamic maximum covering location problems. Comput. Oper. Res. 167:106673.Crossref, Google Scholar
• Li R, Nadarajah S (2020) A review of Student’s t distribution and its generalizations. Empirical Econom. 58(3):1461–1490.Crossref, Google Scholar
• Li WWL, Shen Y, Zhang YJ, Win MZ (2013) Robust power allocation for energy-efficient location-aware networks. IEEE/ACM Trans. Networking 21(6):1918–1930.Crossref, Google Scholar
• Li X, Zhao Z, Zhu X, Wyatt T (2011) Covering models and optimization techniques for emergency response facility location and planning: A review. Math. Methods Oper. Res. 74:281–310.Crossref, Google Scholar
• Ljubić I, Putz P, Salazar-González JJ (2012) Exact approaches to the single-source network loading problem. Networks 59(1):89–106.Crossref, Google Scholar
• Ljubić I, Pozo MA, Puerto J, Torrejón A (2024) Benders decomposition for the discrete ordered median problem. Eur. J. Oper. Res. 317(3):858–874.Crossref, Google Scholar
• Maher SJ (2021) Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework. Eur. J. Oper. Res. 290(2):479–498.Crossref, Google Scholar
• Marianov V (2017) Location Models for Emergency Service Applications, INFORMS TutORials in Operations Research (INFORMS, Catonsville, MD), 237–262.Link, Google Scholar
• Mitropoulos P, Mitropoulos I, Giannikos I, Sissouras A (2006) A biobjective model for the locational planning of hospitals and health centers. Health Care Management Sci. 9:171–179.Crossref, Google Scholar
• Moore GC, ReVelle C (1982) The hierarchical service location problem. Management Sci. 28(7):775–780.Link, Google Scholar
• Plane DR, Hendrick TE (1977) Mathematical programming and the location of fire companies for the Denver fire department. Oper. Res. 25(4):563–578.Link, 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
• 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
• Snyder SA, Haight RG (2016) Application of the maximal covering location problem to habitat reserve site selection: A review. International Regional Sci. Rev. 39(1):28–47.Crossref, Google Scholar
• Sorensen P, Church R (2010) Integrating expected coverage and local reliability for emergency medical services location problems. Socio-econom. Planning Sci. 44(1):8–18.Crossref, Google Scholar
• Tanınmış K, Aras N, Güney E, Sinnl M (2024) Benders decomposition algorithms for minimizing the spread of harmful contagions in networks. Comput. Oper. Res. 167:106675.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
• Wang YR, Chen WK, Ljubić I (2025) An efficient branch-and-cut algorithm for the multiple probabilistic covering location problem. Preprint, submitted November 21, https://arxiv.org/abs/2511.17128.Google Scholar
• Wang W, Wu S, Wang S, Zhen L, Qu X (2021) Emergency facility location problems in logistics: Status and perspectives. Transportation Res. Part E Logist. Transportation Rev. 154:102465.Crossref, Google Scholar
• Wentges P (1996) Accelerating Benders’ decomposition for the capacitated facility location problem. Math. Methods Oper. Res. 44:267–290.Crossref, Google Scholar
• Zhang B, Peng J, Li S (2017) Covering location problem of emergency service facilities in an uncertain environment. Appl. Math. Model. 51:429–447.Crossref, Google Scholar