L'équipe "Théorie des Graphes et Optimisation Combinatoire" (GraphComb) a pour objectif le développement de recherches en théorie des graphes et en optimisation combinatoire déterministe et stochastique, et l'application d'une partie de ces recherches à la résolution de problèmes pratiques (réseaux, planification, allocation de ressources). L'équipe distingue ainsi trois axes principaux de recherche :

• Théorie des graphes


• Optimisation combinatoire déterministe


• Optimisation combinatoire stochastique

Théorie des graphes

En ce qui concerne la théorie des graphes l'équipe s'intéresse à des problèmes classiques sous leurs développements les plus récents. Une description commune à beaucoup de ces problèmes est la suivante : étant donnée telle structure, un graphe la contient-il ? Comment la détecter, voire la construire, et éventuellement estimer combien de fois elle est présente ? Comment trouver dans le graphe une structure voisine ?

On cherche aussi à évaluer grâce à diverses techniques (combinatoires, algébriques, algorithmiques, etc...) des paramètres liés à certaines propriétés du graphe et à étudier les relations et les interactions existant entre les divers paramètres.

En fait ces deux points de vue, étude de structures et de paramètres, induisent souvent deux approches complémentaires d'une même question. Par exemple, rechercher si un graphe est hamiltonien ou quelle est la valeur de sa circonférence relève de la même idée et des mêmes techniques. Dans les deux cas, nous sommes parfois conduits à mettre en lumière des classes de graphes dans lesquelles certains paramètres sont plus aisément évalués, ou certaines structures plus facilement détectées.

Les structures et paramètres intéressants varient selon les applications envisagées car les graphes présentent une grande souplesse d'utilisation. Les sujets d'étude abordés étant trop nombreux pour pouvoir être tous décrits (voir la bibliographie des participants), nous citerons seulement quatre sous-axes de recherche importants pour notre groupe. Comme exemples d'autres domaines de travail, on peut citer les nombreuses études menées dans des classes de graphes spécifiques et celles portant sur des paramètres de coloration, distance ou toughness ou sur l'existence de certains facteurs.

• Cycles dans les graphes et graphes orientés


• Décompositions et placements


• Aspects algébriques


• Concepts issus de la domination

Optimisation combinatoire déterministe

Une partie de l’équipe s’intéresse aux méthodes et algorithmes de résolution de problèmes combinatoires. Il s’agit soit de problèmes de graphes (coupe maximale, partitionnement, multiflots), soit de problèmes d’optimisation combinatoire classiques (affectation quadratique, problème du sac-à-dos), pour lesquels l’équipe propose soit de nouvelles relaxations (plus particulièrement des relaxations semi-définies positives), soit des algorithmes efficaces. Dans cette thématique, l’équipe s’intéresse à la prise en compte de l’incertitude à travers l’optimisation robuste.

Les principaux sous-axes de recherche de l'équipe sont :

• Relaxation semi-définie positive


• Optimisation robuste


• Algorithmes d’approximation

Optimisation combinatoire stochastique

Dans le prolongement de l’optimisation robuste et de la prise en compte de l’incertitude, nous nous intéressons aux méthodes et algorithmes de résolution de problèmes d’optimisation combinatoire stochastique où un sous-ensemble de paramètres est représenté par des variables aléatoires. Nos travaux portent sur les méthodes de résolution de problèmes stochastiques à deux (ou plusieurs) niveaux avec recours ainsi que sur la prise en compte de contraintes probabilistes pour la modélisation du risque.

Les principaux sous-axes de recherche de l’équipe sont :

• Méthodes et algorithmes de résolution de problèmes stochastiques à deux niveaux


• Modélisation du risque et prise en compte de contraintes probabilistes