Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

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 . . . . . . . . . . . . . . . . . 57
4.8 The Column Procedure . . . . . . . . . . . . . . . . . . . . 60vi
4.9 The Rounding Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.11 et remarques . . . . . . . . . . . . . . . . . . . . . . . . . 66
CHAPITRE 5 : APPROCHE D’OPTIMISATION HIÉRARCHIQUE POUR
UN PROBLÈME D’ALLOCATION DE RESSOURCES DANS
UN RÉSEAU OPTIQUE OÙ LE ROUTAGE ET LE GROUPAGE
DU TRAFIC EST RÉSOLU PAR GÉNÉRATION DE COLONNES
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 68
5.1 Présentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.2 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.3 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.4 Descriptions of the GRWA, GR, and WA Problems . . . . . . . . . . . 71
5.5 Solving the Grooming and Routing Problem by Column Generation . . 73
5.6 Computational Results and Conclusions . . . . . . . . . . . . . . . . . 76
5.7 Appendix: Additional Tests . . . . . . . . . . . . . . . . . . . . . . . . 79
5.7.1 Impact of Valid Inequalities on Dual Bounds . . . . . . . . . . 79
5.7.2 Impact Of Valid and Selection Criterion on Primal
Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.8 Conclusions et remarques . . . . . . . . . . . . . . . . . . . . . . . . . 86
CHAPITRE 6 : APPROCHES DE REFORMULATION ET DE DÉCOM-
POSITION POUR LE ROUTAGE DU TRAFIC DANS LES
RÉSEAUX OPTIQUES : : : : : : : : : : : : : : : : : : : 88
6.1 Présentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.2 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.3 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.4 Description of the GRWA Problem . . . . . . . . . . . . . . . . . . . . 95
6.5 Dantzig-Wolfe Reformulations . . . . . . . . . . . . . . . . . . . . . . 103
6.5.1 Grooming Pattern Formulation . . . . . . . . . . . . . . . . . . 103
6.5.2 Wavelength Routing Configuration Formulation . . . . . . . . . 108vii
6.6 Benders’ Decomposition and Hierarchical Optimization . . . . . . . . . 109
6.6.1 Grooming and Physical Routing First, Wavelength Assignment
Second . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.6.2 Grooming and Virtual Routing First, Path and Wavelength As-
signment Second . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.7 Implementation Features . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.7.1 Enhanced Demand Covering Constraints . . . . . . . . . . . . 114
6.7.2 Domain Reduction for Bandwidth Reservations . . . . . . . . . 115
6.7.3 Zero-One Extended Formulation . . . . . . . . . . . . . . . . . 118
6.7.4 Valid Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.7.5 Optimizing Bandwidth Reservation on a Grooming Pattern . . . 122
6.7.6 Generating Wavelength Configuration . . . . . . . . . . . . . . 124
6.8 Selected Models and Algorithms . . . . . . . . . . . . . . . . . . . . . 126
6.8.1 A Cutting Plane Approach for the Virtual Routing Formulation . 126
6.8.2 A Column and Cut Generation Approach for the Wavelength
Routing Configuration Formulation . . . . . . . . . . . . . . . 128
6.8.3 A Cutting Plane Hierarchical Optimization Approach for the
Grooming and Physical Routing Formulation . . . . . . . . . . 130
6.8.4 A Column and Cut Generation Hierarchical Optimization Ap-
proach for the Grooming Pattern Formulation . . . . . . . . . . 130
6.9 Numerical Results and Comparison . . . . . . . . . . . . . . . . . . . 131
6.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.11 Appendix 1: Additional Results for the Grooming Pattern Formulation . 139
6.11.1 Impact of Valid Inequalities on Dual Bounds . . . . . . . . . . 139
6.11.2 Impact of Valid Inequalities and Selection Criterion on Primal
Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.12 Appendix 2: Additional Results for the Grooming and Path Routing For-
mulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.13 Appendix 3: Additional Results for the Virtual Routing Formulation . . 150
6.14 Conclusions et remarques . . . . . . . . . . . . . . . . . . . . . . . . . 150viii
CHAPITRE 7 : APPROCHE HIÉRARCHIQUE POUR UN PROBLÈME
DANS LES RÉSEAUX WDM AVEC CONTRAINTES DE
DÉLAIS : : : : : : : : : : : : : : : : : : : : : : : : : : : 156
7.1 Présentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7.2 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7.3 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.4 Statement and Mathematical Formulation of GRWA . . . . . . . . . . . 160
7.5 Hierarchical Optimization Procedure . . . . . . . . . . . . . . . . . . . 161
7.6 Computational Results . . . . . . . . . . . . . . . . . . . . . . . . . . 169
7.6.1 Network and Traffic Instances . . . . . . . . . . . . . . . . . . 169
7.6.2 Impact of the Hop Constraints on the Solution Quality . . . . . 171
7.6.3 Impact of the Physical Path Length Constraints on Solution Quality176
7.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
7.8 Conclusions et remarques . . . . . . . . . . . . . . . . . . . . . . . . . 177
CHAPITRE 8 : CONCLUSIONS : : : : : : : : : : : : : : : : : : : : : : 179
BIBLIOGRAPHIE : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 183LISTE DES TABLEAUX
3.I Traffic instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.II Comparative results. . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.I Traffic instances. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.II Column generation results. . . . . . . . . . . . . . . . . . . . . . . . . 62
4.III Rounding heuristic with optimal master LP solution. . . . . . . . . . . 65
4.IV with column limit. . . . . . . . . . . . . . . . . . . 65
4.V Rounding heuristic with single and two-hop GP. . . . . . . . . . . . . . 65
5.I Comparison of the impact of the different cut classes on the optimality
gap. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.II Master LP without valid inequalities. . . . . . . . . . . . . . . . . . . 80
5.III Master LP with cut set . . . . . . . . . . . . . . . . . . . 80
5.IV Master LP with(s;d) inequalities. . . . . . . . . . . . . . . . . . . . . 80
5.V Master LP with(s;d;t) . . . . . . . . . . . . . . . . . . . 81
5.VI Master LP with load inequalities. . . . . . . . . . . . . . . . . . . . . 81
5.VII Master LP with every . . . . . . . . . . . . . . . . . . . . 81
5.VIII Improvement of dual bounds. . . . . . . . . . . . . . . . . . . . . . . 82
5.IX Primal bounds obtained without cuts and selection criteria(i). . . . . . 85
5.X Primal bounds without cuts and criteria(ii). . . . . . 85
5.XI Primal bounds obtained without cuts and selection criteria(iii). . . . . . 85
5.XII Primal bounds with every cuts and selection criteria(i). . . . . 86
5.XIIIPrimal bounds obtained with every cuts and criteria(ii). . . . 86
5.XIVPrimal bounds with every cuts and selection criteria(iii). . . . 86
5.XV Primal bounds obtained from the rounding heuristic. . . . . . . . . . . 87
6.I An example of demand vector for different granularities and associated
capacity reservation bounds. . . . . . . . . . . . . . . . . . . . . . . . 118
6.II Instances characteristics and associated dual and primal bounds. . . . . 132x
6.III Comparing dual bound at the root node. . . . . . . . . . . . . . . . . . 133
6.IV dual bounds obtained after running CPLEX default branch-
and-cut for 1 hour. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.V Comparing primal bounds PB obtained with the primal heuristics of this
paper without adding cutting planes before hand. . . . . . . . . . . . . 134
6.VI Comparing primal bound PB obtained with the primal heuristics of this
paper applied after running the cutting plane procedure of this paper. . . 135
6.VII Master LP solution without any cut. . . . . . . . . . . . . . . . . . . . 142
6.VIIIMaster LP solution with cut set inequalities. . . . . . . . . . . . . . . . 142
6.IX Master LP solution without(s;d)-lightpath inequalities . . . . . . . . . 142
6.X Master LP solution with k-lightpath inequalities. . . . . . . . . . . . . . 143
6.XI Master LP solution with bandwidth reservation upper bound inequalities. 143
6.XII Master LP solution with every inequalities. . . . . . . . . . . . . . . . 143
6.XIII Improvement of dual bounds. . . . . . . . . . . . . . . . . . . . . . . 144
6.XIVPrimal bounds obtained with criterion (1) and without valid inequalities. 146
6.XVPrimal bounds with criterion (2) and without valid 146
6.XVI Primal bounds obtained with criterion (3) and without valid inequalities. 147
6.XVII Primal bounds with (1) and with every valid inequal-
ities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.XVIIIPrimal bounds obtained with criterion (2) and with every valid in-
equalities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.XIXPrimal bounds obtained with criterion (3) and with every valid inequalities.148
6.XXPrimal bounds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.XXI Base formulation results. . . . . . . . . . . . . . . . . . . . . . . . . 150
6.XXII Impact of cut set inequalities. . . . . . . . . . . . . . . . . . . . . . . 151
6.XXIII Impact of linking . . . . . . . . . . . . . . . . . . . . . 151
6.XXIV Impact of k-demand inequalities. . . . . . . . . . . . . . . . . . . . 151
6.XXV Impact of k-split c-strong inequalities. . . . . . . . . . . . . . . . . . 152
6.XXVI Impact of knapsack cover . . . . . . . . . . . . . . . . 152
6.XXVIIImpact of every inequalities. . . . . . . . . . . . . . . . . . . . . . . 152

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin