A branch-and-cut for the Non-Disjoint m-Ring-Star Problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 2, pp. 167-188.

In this article we study the realistic network topology of Synchronous Digital Hierarchy (SDH) networks. We describe how providers fulfill customer connectivity requirements. We show that SDH Network design reduces to the Non-Disjoint m-Ring-Star Problem (NDRSP). We first show that there is no two-index integer formulation for this problem. We then present a natural 3-index formulation for the NDRSP together with some classes of valid inequalities that are used as cutting planes in a Branch-and-Cut approach. We propose a polyhedral study of a polytope associated with this formulation. Finally, we present our Branch-and-Cut algorithm and give some experimental results on both random and real instances.

DOI : 10.1051/ro/2014006
Classification : 90B10, 90C10, 90C57, 90C90
Mots-clés : realistic SDH network, non-disjointm-ring-star problem, polyhedral approach, branch-and-cut algorithm 
@article{RO_2014__48_2_167_0,
     author = {Fouilhoux, Pierre and Questel, Aur\'elien},
     title = {A branch-and-cut for the {Non-Disjoint} $m${-Ring-Star} {Problem}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {167--188},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {2},
     year = {2014},
     doi = {10.1051/ro/2014006},
     zbl = {1292.90069},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2014006/}
}
TY  - JOUR
AU  - Fouilhoux, Pierre
AU  - Questel, Aurélien
TI  - A branch-and-cut for the Non-Disjoint $m$-Ring-Star Problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2014
SP  - 167
EP  - 188
VL  - 48
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2014006/
DO  - 10.1051/ro/2014006
LA  - en
ID  - RO_2014__48_2_167_0
ER  - 
%0 Journal Article
%A Fouilhoux, Pierre
%A Questel, Aurélien
%T A branch-and-cut for the Non-Disjoint $m$-Ring-Star Problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2014
%P 167-188
%V 48
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2014006/
%R 10.1051/ro/2014006
%G en
%F RO_2014__48_2_167_0
Fouilhoux, Pierre; Questel, Aurélien. A branch-and-cut for the Non-Disjoint $m$-Ring-Star Problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 2, pp. 167-188. doi : 10.1051/ro/2014006. http://www.numdam.org/articles/10.1051/ro/2014006/

[1] T. Achterberg, SCIP: solving constraint integer programs. Math. Program. Comput. 1 (2009) 1-41. | MR | Zbl

[2] P. Augerat, J.M. Belenguer, E. Benavent, A. Corberán and D. Naddef, Separating capacity constraints in the CVRP using tabu search. Eur. J. Oper. Res. 106 (1998) 546-557. | Zbl

[3] M. Baïou and A.R. Mahjoub, The Steiner traveling salesman polytope and related polyhedra. SIAM J. Opt. 13 (2002) 498. | MR | Zbl

[4] R. Baldacci, M. Dell'Amico and J.S. Gonzalez, The capacitated m-ring-star problem. Oper. Res. 55 (2007) 1147. | MR | Zbl

[5] R. Baldacci, E. Hadjiconstantinou and A. Mingozzi, An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52 (2004) 723-738. | MR | Zbl

[6] G. Cornuejols and F. Harche, Polyhedral study of the capacitated vehicle routing problem, on the p-median polytope. Math. Program. 60 (1991) 21-52. | MR | Zbl

[7] B. Dezső, A. Jüttner and P. Kovács, Lemon-an open source c++ graph template library. Electronic Notes in Theoretical Comput. Sci. 264 (2011) 23-45.

[8] R. Fukasawa, H. Longo, J. Lysgaard, M.P. Aragão, M. Reis, E. Uchoa and R.F. Werneck, Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. program. 106 (2006) 491-511. | MR | Zbl

[9] M.R. Garey and D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences. WH Freeman and Company, San Francisco, Ca (1979). | MR | Zbl

[10] E.A. Hoshino and C.C. De Souza, A branch-and-cut-and-price approach for the capacitated m-ring-star problem. Discrete Appl. Math. 160 (2012) 2728-2741. | MR | Zbl

[11] S. Kedad-Sidhoum and V.H. Nguyen, An exact algorithm for solving the ring star problem. Optimization 59 (2010) 125-140. | MR | Zbl

[12] M. Labbé, G. Laporte, I.R. Martin and J.J.S. González, The ring star problem: Polyhedral analysis and exact algorithm. Networks 43 (2004) 177-189. | MR | Zbl

[13] G. Laporte, The vehicle routing problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. 59 (1992) 345-358. | Zbl

[14] A.N. Letchford and J.J. Salazar-Gonzalez. Projection results for vehicle routing. Math. Program. 105 (2006) 251-274. | MR | Zbl

[15] V. Hung Nguyen and M. Minoux, New formulation for the sonet/sdh network design problem, in Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (2006).

[16] P. Soriano, C. Wynants, A. Seguin et al. Design and dimensionning of survivable SDH/SONET networks, in Telecommunications network planning (1999), pp. 147-167.

Cité par Sources :