Hop‐level flow formulation for the survivable network design with hop constraints problem. Issue 2 (7th September 2012)

• Record Type: Journal Article
• Authors: Mahjoub, A. Ridha; Simonetti, Luidi; Uchoa, Eduardo; Gouveia, Luis; Voß, Stefan
• Is Part Of: Networks. Volume 61:Issue 2(2013:Mar.)
• Page Start: 171
• Page End: 179
• Publication Date: 2012-09-07
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21483
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>The hop‐constrained survivable network design problem consists of finding a minimum cost subgraph containing <italic>K</italic> edge‐disjoint paths with length at most <italic>H</italic> joining each pair of vertices in a given demand set. When all demands have a common vertex, the instance is said to be rooted. We propose a new extended formulation for the rooted case, called hop‐level multicommodity flow (MCF), that can be significantly stronger than the previously known formulations, at the expense of having a larger number of variables and constraints, growing linearly with the number of edges and demands and quadratically with <italic>H</italic>. However, for the particular case where <italic>H</italic> = 2, it can be specialized into a very compact and efficient formulation. Even when <italic>H</italic> = 3, hop‐level‐MCF can still be quite efficient and it has solved several instances from the literature for the first time. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013</p> </abstract>