{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T06:17:00Z","timestamp":1764656220355,"version":"3.37.3"},"reference-count":32,"publisher":"EDP Sciences","issue":"5","license":[{"start":{"date-parts":[[2022,9,26]],"date-time":"2022-09-26T00:00:00Z","timestamp":1664150400000},"content-version":"vor","delay-in-days":25,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2022,8,22]]},"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>In this paper, we study a variant of the survivable network design problem, that is the survivable network design problem with labels (colors) on the edges. In particular, we address the Generalized Labeled Two Edge Connected Subgraph Problem (GLTECSP) that has many applications in telecommunication and transportation. Given a connected undirected graph<jats:italic>G<\/jats:italic>such that with each edge is associated a set of labels (colors), the GLTECSP consists in finding a two-edge connected spanning subgraph of<jats:italic>G<\/jats:italic>with a minimum number of distinct labels. We propose two Integer Programming (IP) formulations for the problem, a natural formulation using cuts on the edges, and a compact formulation using color-cuts. We devise Branch-and-Cut algorithms to solve both formulations and compare them on sets of randomly generated instances. Computational results show that the compact formulation outperforms the natural one regarding the linear relaxation and the computational time. Moreover, the compact formulation is able to solve to optimality several instances left unsolved within the time limit by the natural formulation.<\/jats:p>","DOI":"10.1051\/ro\/2022146","type":"journal-article","created":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T07:55:23Z","timestamp":1661414123000},"page":"3393-3404","source":"Crossref","is-referenced-by-count":2,"title":["The edge-labeled survivable network design problem: Formulations and branch-and-cut"],"prefix":"10.1051","volume":"56","author":[{"given":"Mariem","family":"Ben Salem","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2377-5709","authenticated-orcid":false,"given":"Raouia","family":"Taktak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fatmah","family":"Almathkour","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2022,9,26]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0895480193259813","volume":"10","author":"Baou","year":"1997","journal-title":"SIAM J. Discrete Math."},{"key":"R2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0012-365X(94)00255-H","volume":"147","author":"Barahona","year":"1995","journal-title":"Discrete Math."},{"key":"R3","doi-asserted-by":"crossref","first-page":"1868","DOI":"10.1111\/itor.12494","volume":"26","author":"Bordini","year":"2019","journal-title":"Int. Trans. Oper. Res."},{"key":"R4","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1137\/0406047","volume":"6","author":"Boyd","year":"1993","journal-title":"SIAM J. Discrete Math."},{"key":"R5","doi-asserted-by":"crossref","first-page":"259","DOI":"10.7151\/dmgt.1053","volume":"17","author":"Broersma","year":"1997","journal-title":"Discuss. Math. Graph Theory"},{"key":"R6","doi-asserted-by":"crossref","first-page":"3082","DOI":"10.1016\/j.cor.2009.02.003","volume":"36","author":"Captivo","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Cerulli R., Fink A., Gentili M. and Vo\u00df S., Metaheuristics comparison for the minimum labelling spanning tree problem. In: The Next Wave in Computing, Optimization, and Decision Technologies. Springer (2005) 93\u2013106.","DOI":"10.1007\/0-387-23529-9_7"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Cerulli R., Fink A., Gentili M. and Vo\u00df S., Extensions of the minimum labelling spanning tree problem. J. Telecommun. Inf. Technol. (2006) 39\u201345.","DOI":"10.26636\/jtit.2006.4.396"},{"key":"R9","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0020-0190(97)00127-0","volume":"63","author":"Chang","year":"1997","journal-title":"Inf. Process. Lett."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Consoli S., P\u00e9rez J.A.M. and Mladenovi\u0107 N., Intelligent optimization for the minimum labelling spanning tree problem. In: International Conference on Learning and Intelligent Optimization. Springer (2013) 19\u201323.","DOI":"10.1007\/978-3-642-44973-4_2"},{"key":"R11","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230230307","volume":"23","author":"Coullard","year":"1993","journal-title":"Networks"},{"key":"R12","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0166-218X(94)00135-Z","volume":"66","author":"Coullard","year":"1996","journal-title":"Discrete Appl. Math."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Da Silva T.G., The Minimum Labeling Spanning Tree and Related Problems. Avignon University, France (2018).","DOI":"10.5753\/ctd.2019.6333"},{"key":"R14","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/s13675-018-0099-5","volume":"7","author":"Da Silva","year":"2019","journal-title":"EURO J. Comput. Optim."},{"key":"R15","unstructured":"Da Silva T.G., Ochi L.S., Michelon P., Gueye S. and Cabral L.A., Solving the minimum labeling global cut problem by mathematical programming. Preprint arXiv:1903.04319 (2019)."},{"key":"R16","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.ejor.2018.09.044","volume":"274","author":"Da Silva","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"R17","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.tcs.2016.07.040","volume":"648","author":"Dutta","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"R18","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.dam.2019.02.038","volume":"281","author":"Faria","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"R19","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"Ford","year":"1956","journal-title":"Can. J. Math."},{"key":"R20","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"Goldberg","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"key":"R21","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"Gomory","year":"1961","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Granata D., Cerulli R., Scutella M.G. and Raiconi A., Maximum flow problems and an np-complete variant on edge-labeled graphs. Handb. Comb. Optim. (2013) 1913\u20131948.","DOI":"10.1007\/978-1-4419-7997-1_64"},{"key":"R23","first-page":"617","volume":"7","author":"Gr\u00f6tschel","year":"1995","journal-title":"Handb. Oper. Res. Manage. Sci."},{"key":"R24","unstructured":"Gusfield D., Very simple algorithms and programs for all pairs network flow analysis. Technical report, Computer Science Division, University of California, Davis, (1987)."},{"key":"R25","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1137\/0219009","volume":"19","author":"Gusfield","year":"1990","journal-title":"SIAM J. Comput."},{"key":"R26","doi-asserted-by":"crossref","first-page":"1534","DOI":"10.1016\/j.cor.2011.01.011","volume":"3","author":"Jozefowiez","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"R27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.20072","volume":"46","author":"Kerivin","year":"2005","journal-title":"Networks: Int. J."},{"key":"R28","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01582572","volume":"64","author":"Mahjoub","year":"1994","journal-title":"Math. Program."},{"key":"R29","unstructured":"Perez J. and Consoli S., On the minimum labelling spanning bi-connected subgraph problem. Preprint arXiv:1505.01742 (2015)."},{"key":"R30","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1002\/net.22057","volume":"79","author":"Vaisman","year":"2022","journal-title":"Networks"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Wen X., Broersma H., Zhang Z.-B. and Zhang X., On the complexity of edge-colored subgraph partitioning problems in network optimization. Discrete Math. Theor. Comput. Sci. 17 (2016). DOI: 10.46298\/dmtcs.2159.","DOI":"10.46298\/dmtcs.2159"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Xiong Y., Golden B. and Wasil E., The colorful traveling salesman problem. In: Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies. Springer (2007) 115\u2013123.","DOI":"10.1007\/978-0-387-48793-9_8"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022146\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T15:23:59Z","timestamp":1727882639000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9]]},"references-count":32,"journal-issue":{"issue":"5"},"alternative-id":["ro220042"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2022146","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2022,9]]}}}