Le 24/04/2018 par Fatiha Bendali :

Résumé :

Nous proposons de faire une analyse  du problème de la k-connexité, k >= 2,  en présence d’un graphe de conflits. En particulier, nous nous intéresserons à l’effet de ces conflits sur les résultats polynomiaux de la 2-connexité d’un point de vue polyèdral. On recherche en particulier des contraintes valides dont l’ajout déterminera les solutions 2-connexes sans conflit. Des procédures de Branch-and-Cut seront mises en œuvre pour valider les performances des modèles établis.

Contexte, enjeux, problématique 

La survie d’un réseau de communications est assurée par l’existence d’un lien ou d’une suite de liens entre tout couple de nœuds du réseau. Cette notion est modélisée par la propriété de connexité dans un graphe où chaque sommet représente un nœud et une arête la communication directe entre deux nœuds.

 La k-connexité dans un graphe est exprimée par l’existence entre tout couple de sommets d’au moins k chaînes arêtes ou sommets disjointes. Etant donné un graphe de communications, on s’intéresse à en extraire un sous graphe couvrant tous les nœuds qui est k-connexe et de coût de construction des arêtes minimum. Ce problème de conception de réseau pour des coûts quelconques avec k>= 2 est NP-difficile. Pour k=1, il correspond à la recherche d’un arbre de poids minimum qui est un problème facile pour lequel existent des algorithmes de construction polynomiaux. Cependant, l’existence de conflits sur des paires de liens dans un réseau de communications peut atténuer les possibilités d’existence même d’une solution réalisable. C’est le cas lorsqu’on cherche un arbre de poids minimum dans un graphe et que certains couples d’arêtes sont incompatibles. Le problème de la recherche d’un arbre couvrant de poids minimum en présence d’un graphe de conflits devient alors NP-difficile. D’autres problèmes classiques d’optimisation combinatoire sous contraintes de conflits ont été étudiés dans la dernière décennie par un certain nombre d’auteurs : le problème du sac à dos (2009), le flot maximum, le bin packing et le couplage parfait de coût minimum en 2013. En 2009 et 2011, Darmann et. Al. ont été parmi les premiers à traiter le problème de l’arbre de poids minimum avec conflit. En particulier, ils ont mis en évidence des structures de graphes de conflits où le problème reste polynomial et ont établi des heuristiques dans d’autres cas. Des modèles mathématiques ont aussi été explorés et testés dans l’objectif d’une résolution exacte.

L’objectif de ce travail est d’explorer le contexte des problèmes d’optimisation combinatoire relatifs à la k-connexité, k >=2,  en présence de contraintes de conflits disjonctives.

Méthodologie proposée 

                       Modélisation par des graphes et des programmes linéaires  

                       Programmation de méthodes exactes et heuristiques. Evaluation de performances des algorithmes utilisés.

 Situation dans le contexte du laboratoire

            Ce sujet se situe dans le thème « Optimisation combinatoire et continue » de l’axe MAAD du LIMOS

Profil du doctorant recherché

Compétences en programmation mathématique et en développement informatique.