A branch-and-cut algorithm for the Multiple Steiner TSP with Order constraints
Borne, Sylvie; Mahjoub, Ali Ridha; Taktak, Raouia (2013), A branch-and-cut algorithm for the Multiple Steiner TSP with Order constraints, Electronic Notes in Discrete Mathematics, 41, p. 487–494. 10.1016/j.endm.2013.05.129
Type
Article accepté pour publication ou publiéDate
2013Journal name
Electronic Notes in Discrete MathematicsVolume
41Publisher
Institute of Mathematical Statistics
Pages
487–494
Publication identifier
Metadata
Show full item recordAuthor(s)
Borne, SylvieMahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Taktak, Raouia
Abstract (EN)
The paper deals with a problem motivated by survivability issues in multilayer IP-over-WDM telecommunication networks. Given a set of traffic demands for which we know a survivable routing in the IP layer, our purpose is to look for the corresponding survivable topology in the WDM layer. The problem amounts to Multiple Steiner TSPs with order constraints. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We also present new valid inequalities and discuss their facial aspect. Based on this, we devise a Branch-and-cut algorithm and present preliminary computational results.Subjects / Keywords
Steiner TSP; travelling salesman problem; IP-over-WDM networks; order constraint; Branch-and-cut algorithmRelated items
Showing items related by title and author.
-
Gabrel, Virginie; Mahjoub, Ali Ridha; Taktak, Raouia; Uchoa, Eduardo (2020) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Taktak, Raouia; Uchoa, Eduardo Communication / Conférence
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
-
Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper