Séminaire Makhlouf Hadji

Jeudi 18 Mars 2010 (15h00)

Makhlouf Hadji, Institut Télécom et Management SudParis (ex-INT), Groupe Algorithmes pour les réseaux, Evry.

Titre : Optimisation des réseaux à composantes unicycliques.

Résumé : Ces travaux s’inscrivent dans le domaine de l’optimisation combinatoire. Ils utilisent l’approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. On introduit et étudie le problème d’optimisation des réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d’autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques.

Nous commencons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithmes sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. D’autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes.