Essec\Faculty\Model\Contribution {#2237
#_index: "academ_contributions"
#_id: "16432"
#_source: array:26 [
"id" => 16432
"slug" => "16432-a-tailored-branch-and-benders-cut-approach-for-backup-covering-problems"
"yearMonth" => "2026-05"
"year" => 2026
"title" => "A Tailored Branch-and-Benders-Cut Approach for Backup Covering Problems"
"description" => "FADDA, E., LJUBIC, I. et MANERBA, D. (2026). A Tailored Branch-and-Benders-Cut Approach for Backup Covering Problems. <i>INFORMS Journal on Computing</i>, In press, pp. 1-19."
"authors" => array:3 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "Fadda Edoardo"
]
2 => array:1 [
"name" => "Manerba Daniele"
]
]
"ouvrage" => ""
"keywords" => array:5 [
0 => "backup covering problems"
1 => "redundant coverage"
2 => "BACOP1"
3 => "BACOP2"
4 => "Benders decomposition"
]
"updatedAt" => "2026-06-04 15:10:32"
"publicationUrl" => "https://doi.org/10.1287/ijoc.2025.1394"
"publicationInfo" => array:3 [
"pages" => "1-19"
"volume" => "In press"
"number" => ""
]
"type" => array:2 [
"fr" => "Articles"
"en" => "Journal articles"
]
"support_type" => array:2 [
"fr" => "Revue scientifique"
"en" => "Scientific journal"
]
"countries" => array:2 [
"fr" => null
"en" => null
]
"abstract" => array:2 [
"fr" => "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."
"en" => "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."
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2026-07-05T23:23:23.000Z"
"docTitle" => "A Tailored Branch-and-Benders-Cut Approach for Backup Covering Problems"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, Fadda Edoardo, Manerba Daniele"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, Fadda Edoardo, Manerba Daniele</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2026</span>"
"keywordList" => "<a href="#">backup covering problems</a>, <a href="#">redundant coverage</a>, <a href="#">BACOP1</a>, <a href="#">BACOP2</a>, <a href="#">Benders decomposition</a>"
"docPreview" => "<b>A Tailored Branch-and-Benders-Cut Approach for Backup Covering Problems</b><br><span>2026-05 | Articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://doi.org/10.1287/ijoc.2025.1394" target="_blank">A Tailored Branch-and-Benders-Cut Approach for Backup Covering Problems</a>"
]
+lang: "fr"
+"_score": 9.018373
+"_ignored": array:2 [
0 => "abstract.en.keyword"
1 => "abstract.fr.keyword"
]
+"parent": null
}
