Two node‐disjoint hop‐constrained survivable network design and polyhedra. Issue 4 (6th April 2016)

• Record Type: Journal Article
• Authors: Diarrassouba, Ibrahima; Kutucu, Hakan; Mahjoub, A. Ridha
• Is Part Of: Networks. Volume 67:Issue 4(2016)
• Page Start: 316
• Page End: 337
• Publication Date: 2016-04-06
• Subjects: survivable network -- node‐disjoint paths -- hop constraint -- polyhedron -- facet -- Branch‐and‐Cut; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21679
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : Given a weighted undirected graph G with a set of pairs of terminals ( s i, t i ), i = 1, …, d, and an integer L ≥ 2, the two node‐disjoint hop‐constrained survivable network design problem is to find a minimum weight subgraph of G such that between every s i and t i there exist at least two node‐disjoint paths of length at most L . This problem has applications in the design of survivable telecommunication 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, and propose a Branch‐and‐Cut algorithm for the problem when L = 3, as well as some computational results. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 316–337 2016