Hop‐level flow formulation for the survivable network design with hop constraints problem. Issue 2 (7th September 2012) - Mahjoub, A. Ridha; Simonetti, Luidi; Uchoa, Eduardo; Gouveia, Luis; Voß, Stefan
Abstract The hop‐constrained survivable network design problem consists of finding a minimum cost subgraph containing K edge‐disjoint paths with length at most H 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 H. However, for the particular case where H = 2, it can be specialized into a very compact and efficient formulation. Even when H = 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