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

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.