Modèles et Algorithmes de Multiflots à Coût discontinu 

pour l’Optimisation de Réseaux de Télécommunications




Thèse de doctorat de l’Université Paris 6 soutenue par Arnaud Knippel le 26 juin 2001 devant le jury composé de :

               N. Maculan        Rapporteur
                P. Tolla             Rapporteur
                S. Fdida       Président du jury
                A. Lisser        Examinateur
                D.T. Pham        Examinateur
                M. Minoux        Directeur
                V. Gabrel        Co-directrice


Résumé

Cette thèse porte sur l’optimisation de réseaux de télécommunications : comment répartir les capacités sur les liens d’un réseau de façon à minimiser le coût global tout en satisfaisant un ensemble de demandes de trafic ? Les coûts sur les liens du réseau sont modélisés ici par des fonctions de coût croissantes en escalier quelconques et le problème est mis sous la forme d’un programme linéaire en nombres entiers. Deux approches distinctes ont donné lieu à des algorithmes originaux de résolution exacte ou approchée pour les problèmes de flot simple puis de multiflot, qui compte tenu des fonctions de coût sont d’une très grande complexité combinatoire.

Le cas du flot simple est traité au moyen d’un algorithme exact d’énumération implicite et par une méthode de génération de contraintes. L’algorithme d’énumération implicite a permis la mise au point d’une méthode de résolution approchée pour le cas du multiflot qui améliore des résultats antérieurs. La méthode de génération de contraintes a pu être adaptée au cas du multiflot et a permis d’obtenir des solutions exactes pour des problèmes de réseaux ayant une vingtaine de sommets et une quarantaine d’arêtes. Cette approche a également été généralisée pour la résolution exacte du problème de dimensionnement de réseaux résistant aux pannes, où l’on veut que toutes les demandes de trafic puissent être satisfaites même en cas de panne sur un lien quelconque du réseau. Enfin, des solutions approchées de bonne qualité sont obtenues par génération de contraintes au moyen d’une résolution approchée des sous-problèmes.

Tous ces algorithmes sont présentés avec des résultats d’expériences numériques réalisées à partir de problèmes générés aléatoirement.