{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T11:14:34Z","timestamp":1781176474592,"version":"3.54.1"},"reference-count":48,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T00:00:00Z","timestamp":1669680000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>This article studies the Generalized Steiner Problem with Node-Connectivity Constraints and Hostile Reliability and introduces a metaheuristic resolution approach based on Greedy Randomized Adaptive Search Procedure and Variable Neighborhood Descent. Under the hostile model, nodes and links are subject to probabilistic failures. The research focuses on studying the relationship between the optimization and the reliability evaluation in a symmetric network design problem. Relevant research questions are addressed, linking the number of feasible networks for the full probabilistic model, the sensitivity with respect to elementary probabilities of operation for both edges and nodes, and the sensitivity of the model with respect to the symmetric connectivity constraints defined for terminal nodes. The main result indicates that, for the hostile model, it is better at improving the elementary probabilities of operation of links than improving the elementary probabilities of Steiner nodes, to meet a required reliability threshold for the designed network.<\/jats:p>","DOI":"10.3390\/sym14122523","type":"journal-article","created":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T04:05:24Z","timestamp":1669781124000},"page":"2523","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reliability Analysis of Survivable Networks under the Hostile Model"],"prefix":"10.3390","volume":"14","author":[{"given":"Sebasti\u00e1n","family":"Laborde","sequence":"first","affiliation":[{"name":"Faculty of Engineering, Universidad de la Rep\u00fablica, Montevideo 11300, Uruguay"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4235-4221","authenticated-orcid":false,"given":"Franco","family":"Robledo","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Universidad de la Rep\u00fablica, Montevideo 11300, Uruguay"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8146-4012","authenticated-orcid":false,"given":"Sergio","family":"Nesmachnow","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Universidad de la Rep\u00fablica, Montevideo 11300, Uruguay"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2022,11,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1379","DOI":"10.1007\/s10586-015-0485-1","article-title":"Holistic multiobjective planning of datacenters powered by renewable energy","volume":"18","author":"Nesmachnow","year":"2015","journal-title":"Clust. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1111\/itor.12294","article-title":"Multiobjective evolutionary algorithms for energy and service level scheduling in a federation of distributed datacenters","volume":"24","author":"Iturriaga","year":"2016","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1134\/S0361768819080127","article-title":"Evolutionary Algorithms for Optimizing Cost and QoS on Cloud-based Content Distribution Networks","volume":"45","author":"Iturriaga","year":"2019","journal-title":"Program. Comput. Softw."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1137\/0403027","article-title":"On the Structure of Minimum-Weight -k-Connected Spanning Networks","volume":"3","author":"Bienstock","year":"1990","journal-title":"SIAM J. Discret. Math."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Tapolcai, J., Hajd\u00fa, Z.L., Pa\u0161i\u0107, A., Ho, P.H., and R\u00f3nyai, L. (2021, January 19\u201322). On Network Topology Augmentation for Global Connectivity under Regional Failures. Proceedings of the IEEE Conference on Computer Communications, Athens, Greece.","DOI":"10.1109\/INFOCOM42981.2021.9488879"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.osn.2010.05.004","article-title":"Logical topology augmentation for guaranteed survivability under multiple failures in IP-over-WDM optical networks","volume":"7","author":"Thulasiraman","year":"2010","journal-title":"Opt. Switch. Netw."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Hershey, J., and Yarlagadda, R. (1986). Network Reliability and Survivability. Data Transportation and Protection, Springer.","DOI":"10.1007\/978-1-4613-2195-8"},{"key":"ref_8","first-page":"99","article-title":"A survey of some network reliability analysis and synthesis results","volume":"54","author":"Boesch","year":"2009","journal-title":"Netw. Int. J."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Li, T., Song, T., and Liang, Y. (2018). Wireless Communications under Hostile Jamming: Security and Efficiency, Springer.","DOI":"10.1007\/978-981-13-0821-5"},{"key":"ref_10","unstructured":"Hoersch, F. (2021). Connectivity Problems in Graph Theory: Structures, Algorithms and Complexity. [Ph.D. Thesis, Universit\u00e9 Grenoble Alpes]."},{"key":"ref_11","first-page":"489","article-title":"A Hostile model for network reliability analysis","volume":"8","author":"Lena","year":"2017","journal-title":"J. Heuristics"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s10479-011-1017-x","article-title":"A new simulation method based on the RVR principle for the rare event network reliability problem","volume":"196","author":"Cancela","year":"2012","journal-title":"Ann. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Mladenovic, N., Sleptchenko, A., Sifaleras, A., and Omar, M. (2021, January 21\u201325). A GRASP\/VND Heuristic for the Generalized Steiner Problem with Node-Connectivity Constraints and Hostile Reliability. Proceedings of the Variable Neighborhood Search, Abu Dhabi, United Arab Emirates.","DOI":"10.1007\/978-3-030-69625-2"},{"key":"ref_14","unstructured":"Colbourn, C. (1987). The Combinatorics of Network Reliability, Oxford University Press."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/net.3230170203","article-title":"Steiner problem in networks: A survey","volume":"17","author":"Winter","year":"1987","journal-title":"Networks"},{"key":"ref_16","unstructured":"Garey, M., and Johnson, D. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman and Co."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.orl.2014.12.014","article-title":"Topological optimization of reliable networks under dependent failures","volume":"43","author":"Barrera","year":"2015","journal-title":"Oper. Res. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1137\/S1052623499363220","article-title":"The Sample Average Approximation Method for Stochastic Discrete Optimization","volume":"12","author":"Kleywegt","year":"2002","journal-title":"SIAM J. Optim."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cancela, H., Guerberoff, G., Robledo, F., and Romero, P. (2018, January 20\u201322). Reliability maximization in stochastic binary systems. Proceedings of the 21st Conference on Innovation in Clouds, Internet and Networks and Workshops, Paris, France.","DOI":"10.1109\/ICIN.2018.8401638"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1007\/s11750-020-00550-5","article-title":"Measuring and optimizing system reliability: A stochastic programming approach","volume":"28","author":"Pulsipher","year":"2020","journal-title":"TOP"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.dam.2019.04.022","article-title":"Classes of uniformly most reliable graphs for all-terminal reliability","volume":"267","author":"Archer","year":"2019","journal-title":"Discret. Appl. Math."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Canale, E., Robledo, F., Romero, P., and Viera, J. (2019, January 19\u201321). Building Reliability-Improving Network Transformations. Proceedings of the 15th International Conference on the Design of Reliable Communication Networks, Coimbra, Portugal.","DOI":"10.1109\/DRCN.2019.8713759"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.cor.2015.05.009","article-title":"On the hop-constrained survivable network design problem with reliable edges","volume":"64","author":"Botton","year":"2015","journal-title":"Comput. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1287\/ijoc.1110.0472","article-title":"Benders decomposition for the hop-constrained survivable network design problem","volume":"25","author":"Botton","year":"2013","journal-title":"INFORMS J. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1080\/01605682.2019.1582587","article-title":"Reliable communication network design: The hybridisation of metaheuristics with the branch and bound method","volume":"71","author":"Ozkan","year":"2020","journal-title":"J. Oper. Res. Soc."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Raayatpanah, M., Kabiri, M., Eshghi, F., Kelarestaghi, M., and Nepomuceno, N. (2022). Design of Survivable Wireless Backhaul Networks With reliability Considerations. SSRN, Available online: https:\/\/papers.ssrn.com\/sol3\/papers.cfm?abstract_id=4051814.","DOI":"10.2139\/ssrn.4051814"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"241","DOI":"10.4236\/am.2014.52026","article-title":"Reliable Network Design Problem under Node Failure with Benders Decomposition","volume":"5","author":"Liu","year":"2014","journal-title":"Appl. Math."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.ress.2017.03.017","article-title":"Time-dependent reliability of wireless networks with dependent failures","volume":"165","author":"Park","year":"2017","journal-title":"Reliab. Eng. Syst. Saf."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"107469","DOI":"10.1016\/j.ress.2021.107469","article-title":"Reliability analysis of a complex system with hybrid structures and multi-level dependent life metrics","volume":"209","author":"Yang","year":"2021","journal-title":"Reliab. Eng. Syst. Saf."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Cancela, H., Murray, L., and Rubino, G. (2022). Reliability Estimation for Stochastic Flow Networks With Dependent Arcs. IEEE Transactions on Reliability, IEEE.","DOI":"10.1109\/TR.2022.3178413"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Canale, E.A., Cancela, H., Piccini, J., Robledo, F., Romero, P., Rubino, G., and Sartor, P. (2015, January 5\u20137). Recursive Variance Reduction method in Stochastic Monotone Binary Systems. Proceedings of the 7th International Workshop on Reliable Networks Design and Modeling (RNDM), Munich, Germany.","DOI":"10.1109\/RNDM.2015.7325220"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1137\/S0097539792236237","article-title":"When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks","volume":"24","author":"Agrawal","year":"1995","journal-title":"SIAM J. Comput."},{"key":"ref_33","unstructured":"Jain, K. (1998, January 8\u201311). A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS \u201998), Washington, DC, USA."},{"key":"ref_34","unstructured":"Rahman, M.S., Sadakane, K., and Sung, W.K. (April, January 31). Designing Survivable Networks with Zero-Suppressed Binary Decision Diagrams. Proceedings of the WALCOM: Algorithms and Computation, Singapore."},{"key":"ref_35","first-page":"27","article-title":"GRASP Algorithms for the edge-survivable Generalized Steiner Problem","volume":"5","author":"Sartor","year":"2012","journal-title":"Int. J. Control. Autom."},{"key":"ref_36","first-page":"285","article-title":"Evaluating simple metaheuristics for the Generalized Steiner Problem","volume":"5","author":"Nesmachnow","year":"2005","journal-title":"J. Comput. Sci. Technol."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1504\/IJMHEUR.2014.068914","article-title":"An overview of metaheuristics: Accurate and efficient methods for optimisation","volume":"3","author":"Nesmachnow","year":"2014","journal-title":"Int. J. Metaheuristics"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Resende, M., and Ribeiro, C. (2016). Optimization by GRASP, Springer.","DOI":"10.1007\/978-1-4939-6530-4"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Burke, E., and Kendall, G. (2005). Variable Neighborhood Search. Search Methodologies, Springer International Publishing.","DOI":"10.1007\/0-387-28356-0"},{"key":"ref_40","first-page":"121","article-title":"A new implementation of Yen\u2019s ranking loopless paths algorithm","volume":"1","author":"Martins","year":"2003","journal-title":"Q. J. Belg. Fr. Ital. Oper. Res. Soc."},{"key":"ref_41","unstructured":"Cancela, H., El Khadiri, M., Rubino, G., and Tuffin, B. (2009, January 27\u201329). A Recursive Variance Reduction Technique with Bounded relative Error for Communication Network Reliability Estimation. Proceedings of the 6th St Petersburg Workshop in Computer Simulation, St. Petersburg, Russia."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/978-3-030-38043-4_16","article-title":"Cluster-UY: Collaborative Scientific High Performance Computing in Uruguay","volume":"Volume 1151","author":"Torres","year":"2019","journal-title":"Supercomputing"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0895480193259813","article-title":"Steiner 2-Edge Connected Subgraph Polytopes on Series-Parallel Graphs","volume":"10","author":"Mahjoub","year":"1997","journal-title":"SIAM J. Discret. Math."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1417","DOI":"10.1016\/j.pnsc.2008.03.028","article-title":"An ant colony optimization method for generalized TSP problem","volume":"18","author":"Yang","year":"2008","journal-title":"Prog. Nat. Sci."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"TSPLIB\u2014A Traveling Salesman Problem Library","volume":"3","author":"Reinelt","year":"1991","journal-title":"ORSA J. Comput."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A Note on Two Problems in Connexion with Graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_47","unstructured":"Cheng, G., and Ansari, N. (2003, January 28\u201330). Finding all hops k-shortest paths. Proceedings of the IEEE Pacific Rim Conference on Communications Computers and Signal Processing, Victoria, BC, Canada."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1002\/net.3230140209","article-title":"A quick method for finding shortest pairs of disjoint paths","volume":"14","author":"Suurballe","year":"1984","journal-title":"Networks"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/12\/2523\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:29:10Z","timestamp":1760146150000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/12\/2523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,29]]},"references-count":48,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["sym14122523"],"URL":"https:\/\/doi.org\/10.3390\/sym14122523","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,29]]}}}