Groupe d’études et de recherche en analyse des décisions

Survivable Network Design Problems And Polyhedra

A. Ridha Mahjoub LAMSADE, Université Paris-Dauphine, France

The introduction of fiber optic technology in telecommunication has increased the need of designing survivable networks. Survivable networks must satisfy some connectivity requirements. That is networks which are still functional after the failure of certain links. More precisely, we are given a graph \(G=(V,E)\) with costs on the edges. For each node \(v\) there is a nonnegative integer \(r(v)\), called connectivity type of \(v\), that represents the importance of communication from and to node \(v\). The survivable conditions require that between every pair of nodes \((s,t)\) there are at least

$$ \min{r(s),r(t)}$$

edge-disjoint paths. The survivable network design problem is to determine a subgraph of \(G\) that minimizes the total cost subject to the survivable conditions.

In this talk we will discuss some variants of this problem. First we consider the 2-edge connected subgraph problem, the case where \(r(v)=2\) for every node. We characterize the graphs for which the linear relaxation of the problem is integral, and present some algorithmic consequences of that characterization. In particular we show that the so-called \(F\)-partition inequalities can, in some cases, be separated in polynomial time. Then we consider the problem when \(r(v)=\) 1 or 2 for every node \(v\). This case is of particular interest to the telecommunication industry. We present a class of inequalities, also called partition inequalities, valid for the problem in this case. And we show that the separation problem for these inequalities reduces to the minimization of a submodular function, and can then be solved in polynomial time. We finally discuss some computatinal issues of these inequalities and present some extentions when length constraints are considered in the network.