Séminaire Ibrahima Diarrassouba - 2

Jeudi 04 Novembre 2010 (14h00)

Ibrahima Diarrassouba, Laboratoire de Mathématiques Appliquées du Havre.

Titre : Problèmes de conception de réseaux fiables et polyêdres.

Résumé : Lors de la conception d'un réseau de télécommunications, les opérateurs s'interessent en premier lieu à déterminer une topologie du réseau qui garantisse son bon fonctionnement en cas de panne d'un ou plusieurs équipements. Un réseau est dit fiable, s'il existe toujours un chemin permettant de router le trafic entre n'importe quelle paire de noeuds du réseau, et ce, lorsqu'un certain nombre de liaisons tombent en panne.

Un réseau est représenté par un graphe G=(V,E), un coût de construction associé à chaque arête du graphe et un vecteur type de connexité qui donne, pour chaque noeud du réseau, le nombre minimum de liaisons devant relier ce noeud au reste du réseau. Le problème de conception de réseau fiable consiste à déterminer un sous-graphe de G satisfaisant les conditions de connexité et dont le coût de construction est minimum. Une des approches qui s'est révélée efficace pour résoudre ce type de problèmes est l'approche dite polyhédrale. Elle consiste à étudier le polyèdre associé au problème c'est-à-dire l'enveloppe convexe des solutions de celui-ci. Dans cet exposé, nous présentons l'approche polyhédrale pour les problèmes d'optimisation combinatoire et décrivons leur application à l'étude des problèmes de conception de réseaux fiables. Nous nous intéresserons en particulier à ce type de problème dans le cas où la connexité des noeuds du réseau est égale à 1 ou 2 et au cas où la connexité de tous les noeuds est egale à un entier k >= 2 (réseau k-arete-connexe). Nous considérons aussi une autre variante du problème où la longueur des chemins est bornée par un entier L.