• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

A branch-and-cut algorithm for the Multiple Steiner TSP with Order constraints

Thumbnail
Date
2013
Dewey
Recherche opérationnelle
Sujet
Steiner TSP; travelling salesman problem; IP-over-WDM networks; order constraint; Branch-and-cut algorithm
Journal issue
Electronic Notes in Discrete Mathematics
Volume
41
Publication date
2013
Article pages
487–494
Publisher
Institute of Mathematical Statistics
DOI
http://dx.doi.org/10.1016/j.endm.2013.05.129
URI
https://basepub.dauphine.fr/handle/123456789/11558
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Borne, Sylvie
Mahjoub, Ali Ridha
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Taktak, Raouia
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.