Extended formulation and Branch-and-Cut-and-Price algorithm for the two connected subgraph problem with disjunctive constraints

Fatmah Almathkour (), Ibrahima Diarrassouba () and Youssouf Hadhbi ()
Additional contact information
Fatmah Almathkour: Kuwait University
Ibrahima Diarrassouba: Le Havre Normandie University
Youssouf Hadhbi: Clermont Auvergne INP

Annals of Operations Research, 2025, vol. 351, issue 1, No 35, 965-991

Abstract: Abstract A graph is said to be two connected if between every pair of nodes there are at least two node-disjoint paths. Given weights on the edges of the graph, the two connected subgraph problem is to find a two connected spanning subgraph of G whose weight is minimum. This problem has many applications in telecommunications. In this paper we consider a new variant of this problem with additional disjunctive constraints (called also conflict constraints) related to the survivability of telecommunication networks. This can be called the Disjunctive Two-Connected Subgraph Problem (DTCSP). First, we give an extended formulation for the problem whose variables are the cycles of the graph. Then, we use a column generation algorithm to solve its linear relaxation, and further show that the pricing reduces to finding a specific cycle in the graph which can be formulated as an integer programming problem. We also describe several valid inequalities for the polytope. Moreover, we study the related separation problems and devise separation routines for these inequalities. Using this, we devise a Branch-and-Cut-and-Price algorithm for the problem along with an extensive experimental study.

Keywords: Two connected graph; Disjunctive constraints; Network design; Survivability; Integer programming; Extended formulation; Cycle; Column generation; Pricing; Valid inequalities; Separation; Algorithm; Branch-and-Cut-and-Price (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06123-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:351:y:2025:i:1:d:10.1007_s10479-024-06123-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06123-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().