• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2013
Journal name
Electronic Notes in Discrete Mathematics
Volume
41
Publisher
Institute of Mathematical Statistics
Pages
487–494
Publication identifier
10.1016/j.endm.2013.05.129
Metadata
Show full item record
Author(s)
Borne, Sylvie

Mahjoub, 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 algorithm

Related items

Showing items related by title and author.

  • Thumbnail
    The Multiple Steiner TSP with order constraints: complexity and optimization algorithms 
    Gabrel, Virginie; Mahjoub, Ali Ridha; Taktak, Raouia; Uchoa, Eduardo (2020) Article accepté pour publication ou publié
  • Thumbnail
    The k-node connected subgraph problem: Polyhedral analysis and Branch-and-Cut 
    Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
  • Thumbnail
    The survivable k-node-connected network design problem: Valid inequalities and Branch-and-Cut 
    Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié
  • Thumbnail
    Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem 
    Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper
  • Thumbnail
    Polyhedral Investigation and Branch-and-Cut Algorithm for the Spectrum Assignment Problem 
    Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2022) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo