The k-edge connected subgraph problem: Valid inequalities and Branch-and-Cut

In this paper we describe a Branch-and-Cut algorithm for the k-edge connected subgraph problem. This problem has applications in the design of survivable telecommunication networks. We introduce a new family of valid inequalities for the associated polytope. We give sufficient conditions for these inequalities to be facet defining and devise separation heuristics to separate them. We present further classes of valid inequalities and also discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we develop a Branch-and-Cut algorithm and present some computational results.