A formulation for a hop constrained survivable network design problem
DOI:
https://doi.org/10.2298/YJOR160512004FKeywords:
network design, hop constrained, survivabilityAbstract
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 NPhard, it is useful to combine the presented formulation with heuristic methods in order to solve effectively large problem instances. The model was tested over the graphs with up to 85 nodes and 148 arcs, in order to validate it in cases with known solution.References
Botton, Q., ”Survivable network design with quality of service constraints”, PhD thesis, Université Catholique de Louvain, Louvain School of Management, 2010.
Botton, Q., Fortz, B., and Gouveia, L., ”On the hop-constrained survivable network design problem with reliable edges”, Centro de Investigação Operacional, Faculdade de Ciências da Universidade de Lisboa, Lisboa, Portugal, 2014. Available at http://www.optimizationonline.org/DB_FILE/2012/04/3424.pdf. Accessed on March 2017.
Botton, Q., Fortz, B., Gouveia, L., and Poss, M., ”Benders decomposition for the hop-constrained survivable network design problem”, INFORMS Journal on Computing, 25 (1) (2013) 13-26.
Gouveia, L., ”Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints”, INFORMS Journal on Computing, 10 (2) (1998) 180–188.
Gouveia, L., Patrício, P., and de Sousa, A., ”Hop-constrained node survivable network design: An application to MPLS over WDM”, Networks and Spatial Economics, 8 (1) (2008) 3–21.
Kerivin, H., and Mahjoub, A., ”Design of survivable networks: A survey”, Networks, 46 (1) (2005) 1–21.
Mahjoub, R., Simonetti, L., and Uchoa, E., ”Hop-level flow formulation for the hop constrained survivable network design problem”, Network Optimization, 2011, 176-181.
Raghavan, S., and Anandalingam, G., ”The Effect of Hop Limits on Optimal Cost in Survivable Network Design”, in: Orlowski, S. and Wessély, R. (eds.) Telecommunications Planning: Innovations in Pricing, Network Design and Management, 2006.
Steiglitz, K., Weiner, P., and Kleitman, D., ”The design of minimum-cost survivable networks”, IEEE Transactions on Circuit Theory, 16 (4) (1969) 455–460.
Stoer, M., Design of survivable networks, volume 1531 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, 1992.
Winter, P., ”Steiner problem in networks: a survey”, Networks, 17 (2) (1987) 129-167.
Downloads
Published
Issue
Section
License
Copyright (c) 2017 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
