LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » News » PhD students

KNIPPEL Arnaud

PhD graduated
Team : DECISION
Departure date : 08/31/2004
Supervision : Michel MINOUX
Co-supervision : GABREL Virginie

Modèles et algorithmes de multiflots à coût discontinu pour l'optimisation réseaux de télécommunications

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ésistants 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.
Defence : 06/26/2001 - Salle 203 - jussieu
Jury members :
Monoux Michel, Professeur UPMC, directeur
Gabrel Virginie, MCF, paris XIII, co-directrice
Maculan Neson, PR Univ. fédérale de Rio, Rapporteur
Tolla Pierre, PR Paris 9, rapporteur
Fdida Serge, PR Paris 6, Président
Lisser Abdel, HDR France Telecom R&D, examinateur

1998-2007 Publications

 Mentions légales
Site map |