Reformulation et décomposition pour un problème d'allocation de ressources dans un réseau optique

Benoît Vignac

Description

Sous la direction de François Vanderbeck, Brigitte Jaumard, Gilbert Laporte
Thèse soutenue le 29 janvier 2010: Bordeaux 1
Les réseaux optiques sont aujourd’hui l’élément de base des systèmes de communica- tions modernes, en particulier l’Internet. Grâce au multiplexage en longueurs d’onde et au groupage du tra?c, la bande passante disponible sur une ?bre optique est supérieure à plusieurs térabits par seconde. Cependant les équipements opto-électroniques qui permettent d’opérer ces réseaux sont très coûteux car il doivent fonctionner à un débit très important. Le problème de groupage et du routage d’un ensemble de requêtes couplé avec l’affectation des longueurs d’onde (GRWA) est donc un problème stratégique de première importance. L’objectif est de minimiser le coût du réseau, évalué comme le nombre de ports optiques installés aux nœuds. Il peut être modélisé sous la forme d’un problème d’allocation de ressources dans un réseau à capacité multi-niveaux avec multi-?ots non bifurqués. Cette catégorie de problème est connue pour être très dif?cile compte tenu de la faiblesse de la relaxation linéaire des formulations associées. Les travaux réalisés durant cette thèse ont consisté en le développement de méthodes de résolution pour ce problème à partir de multiples techniques de recherche opéra- tionnelle : méta-heuristique de type recherche avec tabous, décomposition de Dantzig- Wolfe, décomposition de Benders, reformulation en variables binaires, méthode de plans coupants, heuristique d’arrondi. Les méthodes résultantes, dont certaines sont hybrides, permettent d’avoir un aperçu des méthodes ef?caces pour ce type de problème. En partic- ulier, les méthodes basées sur la décomposition de Benders, qui donnent lieu à des procédures d’optimisation hiérarchique dans lesquelles l’affectation de longueurs d’onde est placée au dernier niveau, sont les méthodes les plus ef?caces car elles permettent de séparer le routage optique du routage physique. En?n, nous utilisons la meilleure méthode de résolution pour observer l’impact des contraintes de délais sur la qualité des solutions.
-Réseau optique WDM
-Génération de colonnes
-Heuristiques primales
-Multiplexage en longueurs d’onde
-Plans coupants
-Groupage du tra?c
-Décomposition de Benders
-Allocation de ressources dans un réseau
Optical networks are the core element of modern communication systems and in particu- lar Internet. With wavelength multiplexing and grooming capability, terabits per second bandwidth can be reached. However, opto-electronic equipment used to operate these networks are very expensive as their bit rate must be very large. The grooming, routing and wavelength assignment (GRWA) problem, which consists in minimizing the net- work cost, evaluated by the number of required optical ports, while guaranteeing that each request is granted, is of great interest. The GRWA problem can be modeled as a multi-layer capacitated network design problem with non-bifurcated multi-?ows. This type of problem is known to be hard to solve as their linear relaxation is weak. The objective of this work was to develop solution methods based on multiple oper- ations research techniques : Tabu search based meta-heuristic, Dantzig-Wolfe decompo- sition, Benders decomposition, 0 1 reformulation, cutting-planes, rounding heuristic. The resulting solution tools, some of them hybrid, give a perspective on the effective solution approaches for this type of problem. From the experiments, it turns out that the methods based on Benders’ decomposition, which lead to hierarchical optimization procedures, are the most ef?cient as they allow to separate the optical routing from the physical routing with the wavelength assignment decisions taken in the lower stage sub- problem. In addition to the approach comparison, we use the most effective method to evaluate the impact of the delay constraints on the solution quality.
-WDMoptical network
-Cutting-planes
-Primal heuristics
-Benders’ decomposition
-Traf?c grooming
-Network design
-Meta-heuristic
-Column generation
Source: http://www.theses.fr/2009BOR13996/document

Sujets

• Génération de colonnes

Informations

• Publié par: Thesee
• Nombre de lectures: 52
• Langue: English

Extrait

Numéro d’ordre : 3996
THÉSE
PRÉSENTÉE À
L’UNIVERSITÉ BORDEAUX 1
ÉCOLDE DOCTORALE DE MATHÉMATIQUES ET INFORMATIQUE
ET
L’UNIVERSITÉ DE MONTRÉAL
DÉPARTEMENT DE D‘’INFORMATIQUE ET DE RECHERCHE
OPÉRATIONNELLE
Par VIGNAC Benoît
DOCTEUR
SPÉCIALITÉ : Mathématiques Appliquées
REFORMULATION ET DÉCOMPOSITION POUR UN
PROBLÈME D’ALLOCATION DE RESSOURCES
DANS UN RÉSEAU OPTIQUE
Thèse dirigée par :
François VANDERBECK, Brigitte JAUMARD et Gilbert LAPORTE
Soutenue le 29 Janvier 2010
Devant la commission d’examen formée de :
M. GENDRON Bernard Université de Montréal Président
BEN-AMEUR Walid Telecom SudParis Rapporteur
STIDSEN Thomas Technical University of Denmark
MILLER Andrew Université Bordeaux 1 Examinateur
GENDREAU Michel Univerasité de Montréal
VANDERBECK François Université Bordeaux 1
LAPORTES Gilbert HEC Montréal
Mme JAUMARD Brigitte Université Concordia
Université Bordeaux 1-Les Sciences et les Technologies au service de l’Homme et de l’environnementRÉSUMÉ
Les réseaux optiques sont aujourd’hui l’élément de base des systèmes de communica-
tions modernes, en particulier l’Internet. Grâce au multiplexage en longueurs d’onde et
au groupage du trafic, la bande passante disponible sur une fibre optique est supérieure
à plusieurs térabits par seconde. Cependant les équipements opto-électroniques qui per-
mettent d’opérer ces réseaux sont très coûteux car il doivent fonctionner à un débit très
important.
Le problème de groupage et du routage d’un ensemble de requêtes couplé avec l’affecta-
tion des longueurs d’onde (GRWA) est donc un problème stratégique de première im-
portance. L’objectif est de minimiser le coût du réseau, évalué comme le nombre de
ports optiques installés aux nœuds. Il peut être modélisé sous la forme d’un problème
d’allocation de ressources dans un réseau à capacité multi-niveaux avec multi-flots non
bifurqués. Cette catégorie de problème est connue pour être très difficile compte tenu de
la faiblesse de la relaxation linéaire des formulations associées.
Les travaux réalisés durant cette thèse ont consisté en le développement de méthodes
de résolution pour ce problème à partir de multiples techniques de recherche opéra-
tionnelle : méta-heuristique de type recherche avec tabous, décomposition de Dantzig-
Wolfe, décomposition de Benders, reformulation en variables binaires, méthode de plans
coupants, heuristique d’arrondi. Les méthodes résultantes, dont certaines sont hybrides,
permettent d’avoir un aperçu des méthodes efficaces pour ce type de problème. En partic-
ulier, les méthodes basées sur la décomposition de Benders, qui donnent lieu à des procé-
dures d’optimisation hiérarchique dans lesquelles l’affectation de longueurs d’onde est
placée au dernier niveau, sont les méthodes les plus efficaces car elles permettent de sé-
parer le routage optique du routage physique. Enfin, nous utilisons la meilleure méthode
de résolution pour observer l’impact des contraintes de délais sur la qualité des solutions.
Mots clés : réseau optique WDM, groupage du trafic, allocation de ressources dans
un réseau, multiplexage en longueurs d’onde, génération de colonnes, décomposition de
Benders, plans coupants, heuristiques primales.ABSTRACT
Optical networks are the core element of modern communication systems and in particu-
lar Internet. With wavelength multiplexing and grooming capability, terabits per second
bandwidth can be reached. However, opto-electronic equipment used to operate these
networks are very expensive as their bit rate must be very large. The grooming, routing
and wavelength assignment (GRWA) problem, which consists in minimizing the net-
work cost, evaluated by the number of required optical ports, while guaranteeing that
each request is granted, is of great interest. The GRWA problem can be modeled as a
multi-layer capacitated network design problem with non-bifurcated multi-flows. This
type of problem is known to be hard to solve as their linear relaxation is weak.
The objective of this work was to develop solution methods based on multiple oper-
ations research techniques : Tabu search based meta-heuristic, Dantzig-Wolfe decompo-
sition, Benders decomposition, 0 1 reformulation, cutting-planes, rounding heuristic.
The resulting solution tools, some of them hybrid, give a perspective on the effective
solution approaches for this type of problem. From the experiments, it turns out that
the methods based on Benders’ decomposition, which lead to hierarchical optimization
procedures, are the most efficient as they allow to separate the optical routing from the
physical routing with the wavelength assignment decisions taken in the lower stage sub-
problem. In addition to the approach comparison, we use the most effective method to
evaluate the impact of the delay constraints on the solution quality.
Keywords : WDM optical network, traffic grooming, network design, meta-heuristic,
column generation, Benders’ decomposition, cutting-planes, primal heuristics.TABLE DES MATIÈRES
RÉSUMÉ : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : ii
ABSTRACT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iii
TABLE DES MATIÈRES : : : : : : : : : : : : : : : : : : : : : : : : : : : : iv
LISTE DES TABLEAUX : : : : : : : : : : : : : : : : : : : : : : : : : : : : ix
LISTE DES FIGURES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : xii
LISTE DES SIGLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : xiii
DÉDICACE : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : xiv
REMERCIEMENTS : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : xv
CHAPITRE 1 : INTRODUCTION : : : : : : : : : : : : : : : : : : : : : 1
CHAPITRE 2 : LE PROBLÈME DE GROUPAGE DANS LES RÉSEAUX
OPTIQUES WDM : : : : : : : : : : : : : : : : : : : : : 7
2.1 Les réseaux optiques WDM et le groupage du trafic . . . . . . . . . . . 7
2.1.1 La technologie WDM . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Groupage du trafic . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 Routage d’une requête . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Revue de la littérature . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 Topologie en anneau . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Hypothèses techniques . . . . . . . . . . . . . . . . . . . . . . 18
2.2.4 Complexité et méthodes de résolution . . . . . . . . . . . . . . 20
2.3 Problème GRWA traité . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 d’allocation de ressources dans un réseau . . . . . . . . . . . 23v
CHAPITRE 3 : RECHERCHE AVEC TABOU POUR LE PROBLÈME DE
GROUPAGE DU TRAFIC DANS LES RÉSEAUX OPTIQUES
WDM : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26
3.1 Présentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 The Greedy Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Request Rerouting Move . . . . . . . . . . . . . . . . . . . . . 29
3.4.2 Port Removal Phase . . . . . . . . . . . . . . . . . . . . . . . 29
3.4.3 Tunnel Rerouting Phase . . . . . . . . . . . . . . . . . . . . . 30
3.4.4 Feasibility Recovery Phase . . . . . . . . . . . . . . . . . . . . 30
3.4.5 Tabu Status and Forbidden Moves . . . . . . . . . . . . . . . . 31
3.4.6 Multiphase Tabu . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Computational Experiments . . . . . . . . . . . . . . . . . . . . . . . 32
3.5.1 Traffic and Network Instances . . . . . . . . . . . . . . . . . . 32
3.5.2 Comparative Heuristic Performances . . . . . . . . . . . . . . 33
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.7 et remarques . . . . . . . . . . . . . . . . . . . . . . . . . 35
CHAPTER 4: DÉCOMPOSITION IMBRIQUÉE POUR UN PROBLÈME
D’ALLOCATION DE RESSOURCES DANS UN RÉSEAU
OPTIQUE : : : : : : : : : : : : : : : : : : : : : : : : : : 36
4.1 Présentation de l’article . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4 Description of the GRWA Problem . . . . . . . . . . . . . . . . . . . . 42
4.5 Column Generation Reformulation . . . . . . . . . . . . . . . . . . . . 47
4.6 The Pricing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.7 Dynamic Generation of Routing Patterns . . . . . . . . . . . . . .