Séminaire Makhlouf Hadji

Jeudi 07 Avril 2011 (14h00, salle G001)

Makhlouf Hadji, Laboratoire Réseaux et Services Multimedia Mobiles, Institut Télécom, Télécom Sud Paris.

Titre : Optimisation des réseaux à composantes unicycliques : méthodes exactes.

 

Résumé : Mes travaux s’inscrivent dans le domaine de l’optimisation combinatoire. On utilise 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, on étudie de nouvelles variantes en intégrant de nouvelles contraintes techniques.

On commence par une contrainte portant sur la taille des cycles. On souhaite 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 polynômiaux 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. On se focalise 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, contraintes 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. En deuxième partie, on s’intéressera au problème classique de tarification des services sous des contraintes de ressources dans un nouvel environnement dit Cloud Computing ou "nuage d’informations". On proposera alors une modélisation par un jeu de Stackelberg/Nash consistant à trouver l’ensemble des meilleures stratégies du fournisseur de services et des usagers. L’équilibre de Nash est alors proposé et des simulations numériques seront données.