Two-edge connected subgraph with bounded rings problem: Polyhedral results and Branch-and-Cut
Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006), Two-edge connected subgraph with bounded rings problem: Polyhedral results and Branch-and-Cut, Mathematical Programming, 105, 1, p. 85-111. http://dx.doi.org/10.1007/s10107-005-0576-5
Type
Article accepté pour publication ou publiéDate
2006Journal name
Mathematical ProgrammingVolume
105Number
1Publisher
Springer
Pages
85-111
Publication identifier
Metadata
Show full item recordAbstract (EN)
We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.Subjects / Keywords
Network models, deterministic; Combinatorial optimization; Polyhedral combinatorics, branch-and-bound, branch-and-cutRelated items
Showing items related by title and author.
-
Pesneau, Pierre; Mahjoub, Ali Ridha; Labbé, Martine; Huygens, David (2007) Article accepté pour publication ou publié
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
-
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié
-
Huygens, David; Labbé, Martine; Mahjoub, Ali Ridha; Pesneau, Pierre (2005) Communication / Conférence
-
Mahjoub, Ali Ridha; McCormick, S. Thomas (2010) Article accepté pour publication ou publié