Abstract FR:

Cette these porte sur l'optimisation de reseaux de telecommunications : comment repartir les capacites sur les liens d'un reseau de facon a minimiser le cout global tout en satisfaisant un ensemble de demandes de trafic ? les couts sur les liens du reseau sont modelises ici par des fonctions de cout croissantes en escalier quelconques et le probleme est mis sous la forme d'un programme lineaire en nombres entiers. Deux approches distinctes ont donne lieu a des algorithmes originaux de resolution exacte ou approchee pour les problemes de flot simple puis de multiflot, qui compte tenu des fonctions de cout sont d'une tres grande complexite combinatoire. Le cas du flot simple est traite au moyen d'un algorithme exact d'enumeration implicite et par une methode de generation de contraintes. L'algorithme d'enumeration implicite a permis la mise au point d'une methode de resolution approchee pour le cas du multiflot qui ameliore des resultats anterieurs. La methode de generation de contraintes a pu etre adaptee au cas du multiflot et a permis d'obtenir des solutions exactes pour des problemes de reseaux ayant une vingtaine de sommets et une quarantaine d'aretes. Cette approche a egalement ete generalisee pour la resolution exacte du probleme de dimensionnement de reseaux resistants aux pannes, ou l'on veut que toutes les demandes de trafic puissent etre satisfaites meme en cas de panne sur un lien quelconque du reseau. Enfin, des solutions approchees de bonne qualite sont obtenues par generation de contraintes au moyen d'une resolution approchee des sous-problemes. Tous ces algorithmes sont presentes avec des resultats d'experiences numeriques realisees a partir de problemes generes aleatoirement.