A formulation for a Hop Constrained Survivable Network Design Problem

  • Graciela Ferreira Leites Facultad de Ingeniería
  • Sergio Nesmachnow
  • Franco Robledo

Abstract

This article presents an integer linear model for the hop constrained node survivable network design problem. The formulation is focused on networks represented by undirected graphs with not rooted demands, considering costs in arcs and in optional (Steiner) nodes too. The proposed model allows setting different values of parameters for constraints between each pair of terminal nodes, including hop length and number of node disjoint paths constraints. This work includes calculating lower and upper bounds to the optimal solution. Since this kind of problems are NP-hard, the formulation presented is useful to be combined with heuristic methods in order to solve effectively large problem instances. The model was tested over graphs up to 85 nodes and 148 arcs, in order to validate it in cases with known solution.

Published
Apr 10, 2017
How to Cite
FERREIRA LEITES, Graciela; NESMACHNOW, Sergio; ROBLEDO, Franco. A formulation for a Hop Constrained Survivable Network Design Problem. Yugoslav Journal of Operations Research, [S.l.], v. 27, n. 4, p. 427–438, apr. 2017. ISSN 2334-6043. Available at: <http://yujor.fon.bg.ac.rs/index.php/yujor/article/view/139>. Date accessed: 29 mar. 2024.
Section
Articles