Two Node-Disjoint Hop-Constrained Survivable Network Design and Polyhedra
Mahjoub, Ali Ridha; Kutucu, Hakan; Diarrassouba, Ibrahima (2013), Two Node-Disjoint Hop-Constrained Survivable Network Design and Polyhedra, Electronic Notes in Discrete Mathematics, 41, p. 551-558. http://dx.doi.org/10.1016/j.endm.2013.05.137
Type
Article accepté pour publication ou publiéExternal document link
http://hal.archives-ouvertes.fr/hal-00874354Date
2013Journal name
Electronic Notes in Discrete MathematicsVolume
41Publisher
Elsevier
Pages
551-558
Publication identifier
Metadata
Show full item recordAbstract (EN)
Given a weighted undirected graph G with a set of pairs of terminals {si, ti}, i = 1, ..., d, and an integer L ≥ 2, the two node-disjoint hop-constrained survivable network design problem (TNHNDP) is to find a minimum weight subgraph of G such that between every si and ti there exist at least two node-disjoint paths of length at most L. This problem has applications to the design of survivable telecommunications networks with QoS-constraints. We discuss this problem from a polyhedral point of view. We present several classes of valid inequalities along with necessary and/or sufficient conditions for these inequalities to be facet defining. We also discuss separation routines for these classes of inequalities. Using this, we propose a Branch-and-Cut algorithm for the problem when L = 3, and present some computational results.Subjects / Keywords
branch and cut; hop constraint; node-disjoint paths; Survivable networkRelated items
Showing items related by title and author.
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Yaman, Hande (2016) Article accepté pour publication ou publié
-
Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié
-
Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem Diarrassouba, Ibrahima; Gabrel, Virginie; Mahjoub, Ali Ridha; Gouveia, Luis; Pesneau, Pierre (2016) Article accepté pour publication ou publié
-
Integer Programming Formulations for the k-Edge-Connected 3-Hop-Constrained Network Design Problem Mahjoub, Ali Ridha; Diarrassouba, Ibrahima; Gabrel, Virginie (2010) Communication / Conférence
-
Bendali, Fatiha; Mahjoub, Ali Ridha; Mailfert, Jean; Diarrassouba, Ibrahima (2010) Article accepté pour publication ou publié