A Branch-and-Cut algorithm for the k-edge connected subgraph problem

Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha

Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010), A Branch-and-Cut algorithm for the k-edge connected subgraph problem, Networks, 55, 1, p. 13-32. http://dx.doi.org/10.1002/net.20310

Type

Article accepté pour publication ou publié

Date

2010

Journal name

Networks

Volume

Number

Publisher

Wiley Periodicals

Pages

13-32

Abstract (EN)

In this article, we consider the k-edge connected subgraph problem from a polyhedral point of view. We introduce further classes of valid inequalities for the associated polytope and describe sufficient conditions for these inequalities to be facet defining. We also devise separation routines for these inequalities and 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.

Subjects / Keywords

Reduction operations; Branch-and-cut; Separation; Facet; Polytope; K-edge connected graph