Séminaire Ibrahima Diarrassouba

Jeudi 06 Mai 2010 (14h00)

Ibrahima Diarrassouba, LAMSADE, Université Paris-Dauphine.

Titre : Problèmes de conception de réseaux fiables avec forte connexité.

Résumé : Dans cet exposé, nous présentons une étude polyhédrale des problèmes de conception de réseaux fiables avec forte connexité. Ces problèmes se posent lors de la conception de réseaux de télécommunications, en particulier, pour déterminer une topologie garantissant le bon fonctionnement du réseau en cas de panne d'une ou plusieurs liaisons. Un réseau 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 qui doivent 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. Ce problème a beaucoup été étudié dans la littérature lorsque le type de connexité est inférieur ou égal à 2 (faible connexité) mais très peu dans le cas où le type de connexité est supérieur ou égal à 3 (forte connexité). Dans cet exposé, nous nous intéressons à ce problème avec forte connexité. En particulier, nous considérons le cas où le type de connexité est le même, et égal à k, pour tous les noeuds du réseau (réseau k-arête-connexe). Nous considérons aussi le cas où la longueur des chemins entre certaines paires de sommets est bornée par un entier L. Pour chacun de ces problèmes, nous étudions le polytope associé. Nous discutons des inégalités valides et des conditions sous lesquelles ces inégalités définissent des facettes. Nous donnons une description complète du polytope du problème dans le cas où la longueur des chemins entre deux sommets fixés s et t est limitée à 3. En utilisant les résultats théoriques obtenus, nous proposons plusieurs algorithmes de Coupes et Branchements pour résoudre ces problèmes.