The edge-labeled survivable network design problem: Formulations and branch-and-cut

¹ FSEGS/MIRACL, Université de Sfax, Sfax, Tunisia
² ISIMS & Sma@rts/CRNS, Université de Sfax, Sfax, Tunisia
³ Department of Statistics and Operations Research, Kuwait University, Kuwait City, Kuwait

^* Corresponding author: raouia.taktak@gmail.com

Received: 23 January 2022
Accepted: 22 August 2022

Abstract

In this paper, we study a variant of the survivable network design problem, that is the survivable network design problem with labels (colors) on the edges. In particular, we address the Generalized Labeled Two Edge Connected Subgraph Problem (GLTECSP) that has many applications in telecommunication and transportation. Given a connected undirected graph G such that with each edge is associated a set of labels (colors), the GLTECSP consists in finding a two-edge connected spanning subgraph of G with a minimum number of distinct labels. We propose two Integer Programming (IP) formulations for the problem, a natural formulation using cuts on the edges, and a compact formulation using color-cuts. We devise Branch-and-Cut algorithms to solve both formulations and compare them on sets of randomly generated instances. Computational results show that the compact formulation outperforms the natural one regarding the linear relaxation and the computational time. Moreover, the compact formulation is able to solve to optimality several instances left unsolved within the time limit by the natural formulation.