{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T04:25:40Z","timestamp":1729052740763},"reference-count":42,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2023,3,3]],"date-time":"2023-03-03T00:00:00Z","timestamp":1677801600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2023,7]]},"abstract":"Abstract<\/jats:title>We are interested in the design of robust (or resilient) capacitated rooted Steiner networks in the case of terminals with uniform demands. Formally, we are given a graph, capacity, and cost functions on the edges, a root, a subset of vertices calledterminals<\/jats:italic>, and a bound on the number of possible edge failures. We first study the problem where and the network that we want to design must be a tree covering the root and the terminals: we give complexity results and propose models to optimize both the cost of the tree and the number of terminals disconnected from the root in the worst case of an edge failure, while respecting the capacity constraints on the edges. Secondly, we consider the problem of computing a minimum\u2010cost survivable network, that is, a network that covers the root and terminals even after the removal of any edges, while still respecting the capacity constraints on the edges. We also consider the possibility of protecting a given number of edges. We propose three different formulations: a bilevel formulation (with an attacker and a defender), a cutset\u2010based formulation and a flow\u2010based one. We compare the formulations from a theoretical point of view, and we propose algorithms to solve them and compare their efficiency in practice.<\/jats:p>","DOI":"10.1002\/net.22143","type":"journal-article","created":{"date-parts":[[2023,3,4]],"date-time":"2023-03-04T06:12:50Z","timestamp":1677910370000},"page":"3-31","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Robust capacitated Steiner trees and networks with\u00a0uniform demands"],"prefix":"10.1002","volume":"82","author":[{"given":"C\u00e9dric","family":"Bentz","sequence":"first","affiliation":[{"name":"CEDRIC CNAM Paris France"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-2250-0538","authenticated-orcid":false,"given":"Marie\u2010Christine","family":"Costa","sequence":"additional","affiliation":[{"name":"CEDRIC CNAM (and ENSTA IP\u2010Paris) Paris France"}]},{"given":"Pierre\u2010Louis","family":"Poirion","sequence":"additional","affiliation":[{"name":"Center for Advanced Intelligence Project, RIKEN Tokyo Japan"}]},{"given":"Thomas","family":"Ridremont","sequence":"additional","affiliation":[{"name":"Artelys Paris France"}]}],"member":"311","published-online":{"date-parts":[[2023,3,3]]},"reference":[{"volume-title":"Networks flows, theory, algorithms, applications","year":"1993","author":"Ahuja R.","key":"e_1_2_10_2_1"},{"key":"e_1_2_10_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.09.012"},{"key":"e_1_2_10_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193259813"},{"key":"e_1_2_10_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.02.023"},{"key":"e_1_2_10_6_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400831050"},{"key":"e_1_2_10_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2020.100607"},{"key":"e_1_2_10_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1030.0065"},{"key":"e_1_2_10_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1200"},{"key":"e_1_2_10_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011390"},{"key":"e_1_2_10_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009893108387"},{"key":"e_1_2_10_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-52119-6_18"},{"key":"e_1_2_10_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1110.0472"},{"key":"e_1_2_10_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02071977"},{"key":"e_1_2_10_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.10.1.1"},{"volume-title":"Foundations of bilevel programming","year":"2002","author":"Dempe S.","key":"e_1_2_10_16_1"},{"volume-title":"Advances in Steiner trees","year":"2013","author":"Du D. Z.","key":"e_1_2_10_17_1"},{"key":"e_1_2_10_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22199-0"},{"key":"e_1_2_10_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2017.07.061"},{"key":"e_1_2_10_20_1","doi-asserted-by":"crossref","first-page":"1429","DOI":"10.1287\/opre.2017.1650","article-title":"A new general\u2010purpose algorithm for mixed\u2010integer bilevel linear programs","volume":"65","author":"Fischetti M.","year":"2017","journal-title":"Oper. Res."},{"volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_10_21_1"},{"key":"e_1_2_10_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580607"},{"key":"e_1_2_10_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230104"},{"key":"e_1_2_10_24_1","first-page":"617","article-title":"Design of survivable networks, handbooks in operations research and management","volume":"7","author":"Grotschel M.","year":"1995","journal-title":"Science"},{"key":"e_1_2_10_25_1","doi-asserted-by":"publisher","DOI":"10.3138\/infor.50.2.095"},{"volume-title":"The Steiner tree problem","year":"1992","author":"Hwang F. K.","key":"e_1_2_10_26_1"},{"key":"e_1_2_10_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20072"},{"key":"e_1_2_10_28_1","doi-asserted-by":"crossref","unstructured":"H.Kerivin D.Nace andJ.Geffard Design of survivable networks with a single facility 2nd Eur. Conf. Univ. Multiserv. Netw. IEEE 2002 pp. 208\u2013218.","DOI":"10.1109\/ECUMN.2002.1002107"},{"key":"e_1_2_10_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejco.2021.100007"},{"key":"e_1_2_10_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O"},{"key":"e_1_2_10_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.22005"},{"key":"e_1_2_10_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2019.06.021"},{"issue":"1","key":"e_1_2_10_33_1","first-page":"96","article-title":"Zur allgemeinen kurventheorie","volume":"10","author":"Menger K.","year":"1927","journal-title":"Fund. Math. Inst. Math. Polish Acad. Sci."},{"key":"e_1_2_10_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080306"},{"key":"e_1_2_10_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/0305215X.2014.992892"},{"key":"e_1_2_10_36_1","unstructured":"T.Polzin Algorithms for the Steiner problem in networks Ph.D. thesis Saarland University 2003."},{"key":"e_1_2_10_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20004"},{"key":"e_1_2_10_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.21.5.531"},{"volume-title":"Combinatorial optimization \u2010 polyhedra and efficiency","year":"2003","author":"Schrijver A.","key":"e_1_2_10_39_1"},{"key":"e_1_2_10_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2019.06.024"},{"key":"e_1_2_10_41_1","unstructured":"SNDlib.SNDlib: library of test instances for survivable fixed telecommunication network design.http:\/\/sndlib.zib.de\/"},{"key":"e_1_2_10_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050054"},{"key":"e_1_2_10_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(93)90236-R"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.22143","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/net.22143","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.22143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T19:15:25Z","timestamp":1729019725000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.22143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,3]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.1002\/net.22143"],"URL":"https:\/\/doi.org\/10.1002\/net.22143","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"type":"print","value":"0028-3045"},{"type":"electronic","value":"1097-0037"}],"subject":[],"published":{"date-parts":[[2023,3,3]]},"assertion":[{"value":"2021-12-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}