Synthèse de réseaux à composantes connexes unicycliques

Cette thèse publiée sur chatpfe.com s’inscrit dans le domaine de l’optimisation combinatoire. Elle a pour object d’étudier la synthèse de réseaux à composantes connexes unicycliques. Elle a été financée par un contrat de recherche avec les laboratoires d’Orange. L’optimisation combinatoire est la science qui consiste à trouver un élément optimal au sens d’un coût donné parmi un ensemble fini d’éléments. L’approche polyèdrale est l’une des techniques permettant de résoudre des problèmes d’optimisation combinatoire. Elle est particulièrement utile pour résoudre des problèmes NP difficiles. Chaque solution réalisable est généralement représentée par un vecteur. L’idée fondamentale des méthodes polyèdrales est d’approcher au mieux l’enveloppe convexe de ces vecteurs et d’optimiser sur cette enveloppe approchée en utilisant la programmation linéaire. Les travaux de cette thèse portent globalement sur des problèmes qui se posent dans le cadre des réseaux de télécommunications. En effet, il s’agit de construire un réseau dont toutes les composantes connexes sont unicycliques. On rappelle qu’un graphe est dit unicyclique si et seulement si il est connexe et contient un seul cycle. La structure du cycle permet d’assurer une certaine sûreté de fonctionnement.

Notions préliminaires

Optimisation des réseaux

Nous traitons dans cette thèse plusieurs problèmes d’optimisation combinatoire qui se posent dans le cadre de l’optimisation des réseaux. Il convient donc de décrire brièvement l’optimisation des réseaux. En réalité la tâche est ardue pour plusieurs raisons. En effet, d’une part les réseaux sont multiples (plusieurs technologies, plusieurs architectures). D’autre part, les problèmes sont différents. Enfin, les outils mathématiques qui sont utilisés sont également très divers. Pour ne pas nous perdre dans les détails, nous allons nous contenter de présenter très brièvement les types de problèmes qu’on cherche généralement à résoudre pour optimiser des réseaux. Un réseau a une structure. Le problème de base consiste à définir la structure ou la topologie du réseau. Ceci revient à imposer des contraintes de connexité, voire de k connexité. On peut également considérer des contraintes de diamètre pour imposer que les communications se fassent en un temps limité (voir [1], [5], [34], [35], [55], [77]). D’autres problèmes de topologie consistent à localiser des équipements d’un type particulier (concentrateurs, noeuds d’accès, etc) [81], [126]. Construire un réseau sous la forme d’un ensemble de réseaux d’accès connectés par une dorsale est un autre exemple de problème de topologie : comment faire ce découpage d’une manière optimale ?. Construire donc la topologie d’un réseau donne lieu à un ensemble de problèmes combinatoires très divers et souvent difficiles à résoudre. Tout devient plus complexe si on intègre un aspect dynamique de configuration des réseaux : des noeuds qui se déplacent ou qui changent de comportement induisant un changement de la topologie. Ré-optimiser la topologie en respectant un certain nombre de contraintes techniques est un challenge d’actualité.

Une fois la topologie fixée, il faut relayer du trafic dans le réseau. En d’autres termes, il faut résoudre des problèmes de routage. Ceci se ramène souvent à des problèmes de flot dans un graphe. Plusieurs types de contraintes peuvent être prises en compte: routage de chaque demande sur un seul chemin [7], routage sur plus court chemin [8], [41], routage avec contraintes de délai [6], routage avec contrainte d’équité [105]. On peut également considérer des contraintes de sécurisation se traduisant par l’obligation de rerouter le trafic en cas de panne de certaines composantes du réseau [10], [91], [99]. Tous ces problèmes de routage peuvent aussi être étudiés dans un contexte incertain, c’est à dire lorsque la matrice de trafic qu’on cherche à écouler dans le réseau n’est pas définie d’une manière précise. On peut par exemple supposer que la matrice de trafic varie dans un polytope et chercher un routage compatible avec toutes ces matrices [9], [107], [114]. Pour router du trafic sur une topologie déterminée, il faut installer des capacités de transmission. Ces capacités sont souvent choisies parmi un ensemble discret. L’optimisation du coût des capacités installées se ramène souvent à un problème de programmation linéaire en nombres entiers. Ces problèmes sont généralement appelés problèmes de dimensionnement. Ils sont en réalité souvent résolus en même temps que les problèmes de routage. Un autre type de problèmes d’optimisation qui se posent dans le contexte des réseaux est le problème de tarification. En effet, un réseau offre des services qui doivent être facturés aux clients. Trouver le bon mode de tarification qui garantit par exemple une certaine équité ou un certain niveau de bénéfice à l’opérateur, se ramène à des problèmes d’optimisation et de théorie des jeux [16]. Les types de problèmes qu’on vient d’exposer peuvent être étudiés séparément ou d’une manière combinée. L’utilisation d’une technologie donnée (Internet, ATM, GSM, UMTS, SDH, etc.) induit des contraintes techniques particulières et donc des problèmes d’optimisation particuliers. Les problèmes d’optimisation de réseaux que nous avons étudiés dans cette thèse sont des problèmes du type topologie.

Méthode de Coupes

Pour un problème d’optimisation combinatoire donné, il est en général difficile de caractériser le polyèdre associé par un système d’inégalités linéaires. De plus, même si ce dernier est caractérisé, le système décrivant le polyèdre peut contenir un nombre exponentiel d’inégalités et donc reste inexploitable pour être résolu comme un programme linéaire. Cependant, une description partielle du polyèdre garantie par la méthode de coupes peut être suffisante pour résoudre le problème jusqu’à l’optimum.

Soit le problème d’optimisation combinatoire suivant :

P = max{wx : Ax ≤ b, x entier} (1.2)

et soit P l’enveloppe convexe des solutions de (1.2). On rappelle que ce problème est équivalent au programme max{wx : x ∈ P}, et que si les inégalités du système Ax ≤ b sont suffisantes pour décrire complètement P, alors tous les points extrêmes du polyèdre {x ∈ R n : Ax ≤ b} sont des entiers, et par conséquent le problème (1.2) est équivalent à la relaxation max{wx : Ax ≤ b}. Néanmoins, ce n’est pas toujours le cas, et le polyèdre {x ∈ Rn : Ax ≤ b} peut bien avoir des points extrêmes fractionnaires. En d’autres mots, il existe une contrainte valide violée par cette solution optimale fractionnaire. Cette dernière peut être ajoutée au système Ax ≤ b, afin de trouver une nouvelle relaxation linéaire plus forte.

Dans la méthode de coupes, l’étape de la génération des contraintes valides est la plus difficile. L’une des premières techniques dont la finalité est d’identifier les contraintes valides pour des programmes en variables entières, a été introduite par Gomory. Ensuite, Chvátal a généralisé cette technique, pour obtenir la méthode bien connue de Chvátal-Gomory.

Méthode de Branch&Cut

La méthode qu’on décrit ici, permet de construire un arbre de résolution (arbre de branch&cut), où chaque sommet de l’arbre correspond à un sous-problème, et le problème initial est associé à la racine de l’arbre. Le principe de cette méthode commence par résoudre initialement la relaxation du problème (1.2). Si la solution trouvée est optimale et contient une variable fractionnaire, qui est sensée être entière, alors un algorithme à plans coupants est appliqué afin de trouver de nouvelles inégalités valides (quelques unes peuvent suffire). Ces dernières sont satisfaites par tous les points entiers, mais violées par la solution courante. Ces inégalités seront ajoutées au programme courant. Par la suite, on utilise une méthode de branchement qui consiste à obtenir de nouveaux noeuds. On résout chaque programme associé à un noeud en y ajoutant un certain ensemble de coupes qui peuvent être valides localement au niveau du noeud courant ainsi que du sous-arbre issu de lui, ou globalement au niveau de tous les noeuds de l’arbre de branch&cut. Lors de la résolution d’un programme associé à un noeud de l’arbre, on calcule une évaluation. Si cette évaluation est supérieure (pour un problème de minimisation) à la borne supérieure calculée avant, alors on coupe ce noeud. Dans le cas contraire, il est exploité à son tour.

On arrête cet algorithme lorsqu’on ne peut plus exploiter un noeud de l’arbre. On prend alors la meilleure solution trouvée.

Remarque : Les coupes qu’on ajoute aux programmes associés aux noeuds de l’arbre de branch&cut peuvent être générées jusqu’à épuisement.

Table des matières

Introduction Générale
1 Notions préliminaires
1.1 Optimisation des réseaux
1.2 Approche polyèdrale
1.2.1 Introduction
1.2.2 Les ensembles et combinaisons convexes
1.2.3 Programmation Linéaire et Optimisation Combinatoire
1.2.4 Polyèdres, Faces et Facettes
1.2.5 Méthode de Coupes
1.2.6 Méthode de Branch&Cut
1.2.7 Séparation et Optimisation
1.3 Problèmes combinatoires importants
1.3.1 Les problèmes de plus court chemin
1.3.1.1 L’algorithme de Dijkstra
1.3.1.2 L’algorithme de Bellman
1.3.1.3 L’algorithme de Bellman-Ford
1.3.2 Problème de l’arbre couvrant de poids minimum
1.3.2.1 Algorithme de Kruskal
1.3.2.2 Algorithme de Prim
1.3.3 Le problème de flot maximum-coupe minimum
1.3.3.1 La méthode de Ford-Fulckerson
1.3.3.2 La Méthode des préflots- Algorithme de Goldberg-Tarjan
1.3.3.3 L’algorithme de Gomory-Hu
1.3.4 Les T-join et T-coupe
1.3.4.1 Le problème de T-coupe de poids minimum .
1.3.4.2 Le problème du T-join de poids minimum
1.3.5 Le problème de couplage
1.3.5.1 Le problème de b-couplage
1.3.6 Le problème du voyageur de commerce
1.4 Réseaux à composantes unicycliques
1.4.1 Les matroïdes
1.4.1.1 Les matroïdes bi-circulaires
1.4.2 Partitionnement des réseaux en composantes unicycliques
1.4.2.1 L’algorithme glouton
1.4.2.2 L’algorithme de couplage maximum de poids minimum
1.5 Spectre des graphes
1.5.1 Quelques liens avec l’optimisation combinatoire
1.5.1.1 Lien avec le diamètre d’un graphe
1.5.1.2 Lien avec le nombre isopérimétrique
1.5.1.3 Lien avec le problème de coupe maximum (Max-Cut)
2 Réseaux à composantes unicycliques avec contrainte sur la taille des cycles
2.1 Introduction
2.2 Notations et Formulation Mathématique
2.3 Inégalités Valides
2.4 Sur la structure faciale de P(G, p)
2.5 Un Algorithme à Plans Coupants
2.5.1 Séparation des inégalités (2.5)
2.5.2 Séparation des inégalités (2.2)
2.5.3 Séparation des inégalités (2.4)
2.5.4 Séparation des inégalités (2.6)
2.5.5 Séparation des inégalités (2.7), (2.8) et (2.9)
2.6 Résultats Expérimentaux
2.7 Conclusion
3 Réseaux à composantes unicycliques avec contraintes de type Steiner
3.1 Introduction
3.2 Une première formulation mathématique
3.3 Complexité et formulation étendue
3.4 Les inégalités valides
3.5 Les algorithmes de séparation
3.5.1 Séparation des contraintes (3.3)
3.5.2 Séparation des contraintes (3.7)
3.6 Extensions et liens avec d’autres problèmes
3.7 Résultats numériques
3.8 Conclusion
4 Réseaux à composantes unicycliques avec de nouvelles contraintes techniques
4.1 Introduction
4.2 Contraintes portant sur les degrés des sommets
4.3 Contrainte portant sur le nombre de composantes unicycliques
4.4 Séparation de certains couples de sommets
4.5 Joindre certains couples de sommets
4.6 Conclusion et perspectives
Conclusion Générale

Télécharger le rapport complet