# A branch-and-cut for the Non-Disjoint m-Ring-Star Problem

Pierre Fouilhoux; Aurélien Questel

RAIRO - Operations Research - Recherche Opérationnelle (2014)

- Volume: 48, Issue: 2, page 167-188
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topFouilhoux, Pierre, and Questel, Aurélien. "A branch-and-cut for the Non-Disjoint m-Ring-Star Problem." RAIRO - Operations Research - Recherche Opérationnelle 48.2 (2014): 167-188. <http://eudml.org/doc/275040>.

@article{Fouilhoux2014,

abstract = {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.},

author = {Fouilhoux, Pierre, Questel, Aurélien},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {realistic SDH network; non-disjointm-ring-star problem; polyhedral approach; branch-and-cut algorithm; non-disjoint -ring-star problem},

language = {eng},

number = {2},

pages = {167-188},

publisher = {EDP-Sciences},

title = {A branch-and-cut for the Non-Disjoint m-Ring-Star Problem},

url = {http://eudml.org/doc/275040},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 2

SP - 167

EP - 188

AB - 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.

LA - eng

KW - realistic SDH network; non-disjointm-ring-star problem; polyhedral approach; branch-and-cut algorithm; non-disjoint -ring-star problem

UR - http://eudml.org/doc/275040

ER -

## References

top- [1] T. Achterberg, SCIP: solving constraint integer programs. Math. Program. Comput.1 (2009) 1–41. Zbl1171.90476MR2520442
- [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. Zbl0991.90028
- [3] M. Baïou and A.R. Mahjoub, The Steiner traveling salesman polytope and related polyhedra. SIAM J. Opt. 13 (2002) 498. Zbl1013.05071MR1951031
- [4] R. Baldacci, M. Dell’Amico and J.S. Gonzalez, The capacitated m-ring-star problem. Oper. Res. 55 (2007) 1147. Zbl1167.90416MR2372283
- [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. Zbl1165.90353MR2091769
- [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. Zbl0790.90029MR1231275
- [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. Zbl1094.90050MR2216792
- [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). Zbl0411.68039MR519066
- [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. Zbl1262.90182MR2971356
- [11] S. Kedad-Sidhoum and V.H. Nguyen, An exact algorithm for solving the ring star problem. Optimization59 (2010) 125–140. Zbl1184.90021MR2765473
- [12] M. Labbé, G. Laporte, I.R. Martin and J.J.S. González, The ring star problem: Polyhedral analysis and exact algorithm. Networks43 (2004) 177–189. Zbl1053.90021MR2050239
- [13] G. Laporte, The vehicle routing problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res.59 (1992) 345–358. Zbl0761.90034
- [14] A.N. Letchford and J.J. Salazar-Gonzalez. Projection results for vehicle routing. Math. Program.105 (2006) 251–274. Zbl1085.90032MR2190821
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.