no. 5
The edge-labeled survivable network design problem: Formulations and branch-and-cut
RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3393-3404

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 G such that with each edge is associated a set of labels (colors), the GLTECSP consists in finding a two-edge connected spanning subgraph of G 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.

DOI : 10.1051/ro/2022146
Classification : 90C10, 90C27, 90C57
Keywords: Labeled graphs, survivable network design, two-edge connected subgraph, integer programming, Branch-and-Cut 
@article{RO_2022__56_5_3393_0,
     author = {Ben Salem, Mariem and Taktak, Raouia and Almathkour, Fatmah},
     title = {The edge-labeled survivable network design problem: {Formulations} and branch-and-cut},
     journal = {RAIRO. Operations Research},
     pages = {3393--3404},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {5},
     doi = {10.1051/ro/2022146},
     mrnumber = {4487868},
     zbl = {1507.90107},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022146/}
}
TY  - JOUR
AU  - Ben Salem, Mariem
AU  - Taktak, Raouia
AU  - Almathkour, Fatmah
TI  - The edge-labeled survivable network design problem: Formulations and branch-and-cut
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 3393
EP  - 3404
VL  - 56
IS  - 5
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022146/
DO  - 10.1051/ro/2022146
LA  - en
ID  - RO_2022__56_5_3393_0
ER  - 
%0 Journal Article
%A Ben Salem, Mariem
%A Taktak, Raouia
%A Almathkour, Fatmah
%T The edge-labeled survivable network design problem: Formulations and branch-and-cut
%J RAIRO. Operations Research
%D 2022
%P 3393-3404
%V 56
%N 5
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022146/
%R 10.1051/ro/2022146
%G en
%F RO_2022__56_5_3393_0
Ben Salem, Mariem; Taktak, Raouia; Almathkour, Fatmah. The edge-labeled survivable network design problem: Formulations and branch-and-cut. RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3393-3404. doi: 10.1051/ro/2022146

[1] M. Baïou and A. R. Mahjoub, Steiner 2 -edge connected subgraph polytopes on series-parallel graphs. SIAM J. Discrete Math. 10 (1997) 505–514. | MR | Zbl

[2] F. Barahona and A. R. Mahjoub, On two-connected subgraph polytopes. Discrete Math. 147 (1995) 19–34. | MR | Zbl

[3] A. Bordini, F. Protti, T. G. Da Silva and G. F. De Sousa Filho, New algorithms for the minimum coloring cut problem. Int. Trans. Oper. Res. 26 (2019) 1868–1883. | MR | Zbl

[4] S. C. Boyd and T. Hao, An integer polytope related to the design of survivable communication networks. SIAM J. Discrete Math. 6 (1993) 612–630. | MR | Zbl

[5] H. Broersma and X. Li, Spanning trees with many or few colors in edge-colored graphs. Discuss. Math. Graph Theory 17 (1997) 259–269. | MR | Zbl

[6] M. E. Captivo, J. C. Clímaco and M. M. Pascoal, A mixed integer linear formulation for the minimum label spanning tree problem. Comput. Oper. Res. 36 (2009) 3082–3085. | MR | Zbl

[7] R. Cerulli, A. Fink, M. Gentili and S. Voß, Metaheuristics comparison for the minimum labelling spanning tree problem. In: The Next Wave in Computing, Optimization, and Decision Technologies. Springer (2005) 93–106.

[8] R. Cerulli, A. Fink, M. Gentili and S. Voß, Extensions of the minimum labelling spanning tree problem. J. Telecommun. Inf. Technol. (2006) 39–45.

[9] R.-S. Chang and S.-J. Lee, The minimum labeling spanning trees. Inf. Process. Lett. 63 (1997) 277–282. | MR | Zbl

[10] S. Consoli, J. A. M. Pérez and N. Mladenović, Intelligent optimization for the minimum labelling spanning tree problem. In: International Conference on Learning and Intelligent Optimization. Springer (2013) 19–23.

[11] C. R. Coullard, A. Rais, R. L. Rardin and D. K. Wagner, Linear-time algorithms for the 2 -connected steiner subgraph problem on special classes of graphs. Networks 23 (1993) 195–206. | MR | Zbl

[12] C. R. Coullard, A. Rais, R. L. Rardin and D. K. Wagner, The dominant of the 2 -connected-steiner-subgraph polytope for W 4 -free graphs. Discrete Appl. Math. 66 (1996) 33–43. | MR | Zbl

[13] T. G. Da Silva, The Minimum Labeling Spanning Tree and Related Problems. Avignon University, France (2018).

[14] T. G. Da Silva, S. Gueye, P. Michelon, L. S. Ochi and L. D. A. F. Cabral, A polyhedral approach to the generalized minimum labeling spanning tree problem. EURO J. Comput. Optim. 7 (2019) 47–77. | MR | Zbl

[15] T. G. Da Silva, L. S. Ochi, P. Michelon, S. Gueye and L. A. Cabral, Solving the minimum labeling global cut problem by mathematical programming. Preprint (2019). | arXiv

[16] T. G. Da Silva, E. Queiroga, L. S. Ochi, L. D. A. F. Cabral, S. Gueye and P. Michelon, A hybrid metaheuristic for the minimum labeling spanning tree problem. Eur. J. Oper. Res. 274 (2019) 22–34. | MR | Zbl

[17] T. Dutta, L. S. Heath, V. A. Kumar and M. V. Marathe, Labeled cuts in graphs. Theor. Comput. Sci. 648 (2016) 34–39. | MR | Zbl

[18] L. Faria, S. Klein, I. Sau, U. S. Souza and R. Sucupira, Maximum cuts in edge-colored graphs. Discrete Appl. Math. 281 (2020) 229–234. | MR | Zbl

[19] L. R. Ford and D. R. Fulkerson, Maximal flow through a network. Can. J. Math. 8 (1956) 399–404. | MR | Zbl

[20] A. V. Goldberg and R. E. Tarjan, A new approach to the maximum-flow problem. J. Assoc. Comput. Mach. 35 (1988) 921–940. | MR | Zbl

[21] R. E. Gomory and T. C. Hu, Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9 (1961) 551–570. | MR | Zbl

[22] D. Granata, R. Cerulli, M. G. Scutella and A. Raiconi, Maximum flow problems and an np-complete variant on edge-labeled graphs. Handb. Comb. Optim. (2013) 1913–1948.

[23] M. Grötschel, C. L. Monma and M. Stoer, Design of survivable networks. Handb. Oper. Res. Manage. Sci. 7 (1995) 617–672. | MR | Zbl

[24] D. Gusfield, Very simple algorithms and programs for all pairs network flow analysis. Technical report, Computer Science Division, University of California, Davis, (1987).

[25] D. Gusfield, Very simple methods for all pairs network flow analysis. SIAM J. Comput. 19 (1990) 143–155. | MR | Zbl

[26] N. Jozefowiez, G. Laporte and F. Semet, A branch-and-cut algorithm for the minimum labeling hamiltonian cycle problem and two variants. Comput. Oper. Res. 3 (2011) 1534–1542. | MR | Zbl

[27] H. Kerivin and A. R. Mahjoub, Design of survivable networks: a survey. Networks: Int. J. 46 (2005) 1–21. | MR | Zbl

[28] A. R. Mahjoub, Two-edge connected spanning subgraphs and polyhedra. Math. Program. 64 (1994) 199–208. | MR | Zbl

[29] J. Perez and S. Consoli, On the minimum labelling spanning bi-connected subgraph problem. Preprint (2015). | arXiv

[30] R. Vaisman, Finding minimum label spanning trees using cross-entropy method. Networks 79 (2022) 220–235. | MR | Zbl

[31] X. Wen, H. Broersma, Z.-B. Zhang and X. Zhang, On the complexity of edge-colored subgraph partitioning problems in network optimization. Discrete Math. Theor. Comput. Sci. 17 (2016). DOI: 10.46298/dmtcs.2159. | MR | Zbl

[32] Y. Xiong, B. Golden and E. Wasil, The colorful traveling salesman problem. In: Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies. Springer (2007) 115–123. | Zbl

Cité par Sources :