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

Abstract

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

How to cite

top

Fouilhoux, 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. [1] T. Achterberg, SCIP: solving constraint integer programs. Math. Program. Comput.1 (2009) 1–41. Zbl1171.90476MR2520442
  2. [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. [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. [4] R. Baldacci, M. Dell’Amico and J.S. Gonzalez, The capacitated m-ring-star problem. Oper. Res. 55 (2007) 1147. Zbl1167.90416MR2372283
  5. [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. [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. [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. [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. [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. [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. [11] S. Kedad-Sidhoum and V.H. Nguyen, An exact algorithm for solving the ring star problem. Optimization59 (2010) 125–140. Zbl1184.90021MR2765473
  12. [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. [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. [14] A.N. Letchford and J.J. Salazar-Gonzalez. Projection results for vehicle routing. Math. Program.105 (2006) 251–274. Zbl1085.90032MR2190821
  15. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.