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

Backup covering problems represent a class of covering location models that are extremely important in applications involving decisions that need to comply with service redundancy. Among these models, the most used are backup covering problem of type 1 (BACOP1) and type 2 (BACOP2), which can be seen as different generalizations of the well-known maximal covering location problem. Given an available budget in terms of facilities to open, BACOP1 aims to maximize the demand covered twice while ensuring that the total demand is covered at least once, whereas BACOP2 aims to maximize a weighted combination of the demand covered once and twice without any guarantee on the single coverage. Despite their practical importance, little attention has been paid to the development of tailored solution algorithms for backup covering problems of such types. In this work, we exploit the special structure of BACOP1 and BACOP2 to derive a branch-and-cut approach based on the separation of different Benders cuts. Different from classical Benders decomposition approaches, the cut separation is performed by leveraging combinatorial properties of the resulting subproblems and not through the solution of a linear program. We analyze the dominance properties of the generated cuts and present an empirical comparison of our approach against a state-of-the-art solver on a comprehensive set of large-scale instances. Notably, although the two problems share strong similarities and are addressed within a unified solution framework, the characteristics of the solution procedures and their computational results differ substantially.

History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1394) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1394). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.