Décomposition de Modèles Graphiques – DE-MO-GRAPH

La résolution de problèmes NP-difficiles constitue toujours un défi sur le plan théorique ainsi que pratique. Ce projet vise à résoudre des problèmes de décision, d'optimisation et de comptage (intégration discrète) exprimés en termes de « modèles graphiques » (réseaux de contraintes ou de fonction de coût, réseaux bayésiens, logique propositionnelle, champs de Markov). Il s'agit de modèles où une fonction conjointe sur un ensemble de variables est décrite comme une combinaison factorisée de fonctions de quelques variables. Cette approche est intensivement utilisée en intelligence artificielle, en physique statistique et en statistique. Le terme « modèle graphique » souligne le fait que cette factorisation définit un (hyper)graphe dont les sommets sont les variables et dont les (hyper)arêtes comprennent les variables de chaque facteur. L'expressivité de ces modèles les rend capables de représenter une très large variété de problèmes réels (en traitement d'image, allocation de ressources, bio-informatique,...).
Mais la résolution de ces problèmes est difficile en termes de complexité : NP-complète pour la décision, NP-difficile pour l'optimisation et #P-complète pour le comptage. Ce projet a pour but de traiter ces questions en exploitant des techniques récentes de décomposition d'(hyper)graphes sur les graphes (ou hypergraphes) induits par chaque modèle graphique. L’intérêt pratique de ces approches n’a été démontré qu’au cours des dix dernières années (avec la seule notion de décomposition arborescente) - tout en soulignant leurs limites actuelles - mais présente un fort potentiel de progrès.

En effet, la communauté de la théorie des graphes a indépendamment produit un grand nombre de résultats au cours de ces dernières années. Ils sont restés pour l’essentiel au niveau d’objets théoriques (cf. branch/clique/rank/boolean/matching/treecut/tree-depth-decompositions pour n'en citer que quelques-unes). Actuellement, les résultats théoriques sur ces décompositions n’ont pas encore été exploités pour améliorer les algorithmes de traitement de modèles graphiques et, a fortiori, pour mener à des systèmes efficaces en pratique. Cela n’est pas surprenant dans la mesure où la plupart de ces résultats ont été obtenus pour des motivations théoriques, sans l'objectif affiché de la résolution des modèles graphiques en pratique. Ce type de situation n'est pas nouveau, la notion de décomposition arborescente avait été introduite et étudiée par Roberston et Seymour comme un outil théorique pour prouver la conjecture de Wagner sur les mineurs de graphes. Cet objet mathématique est désormais un outil de base pour les méthodes de résolution qui exploitent la structure des modèles graphiques à traiter.

Sur cette base, un vaste champ d'étude est désormais ouvert autour de la décomposition de graphes, champ qui combine théorie, résultats algorithmiques et outils de résolution pratique. Les objectifs du projet se déclinent donc sur trois axes principaux:

(1) Sur le plan théorique, le but est d'étudier les décompositions existantes ou définir de nouvelles approches de décomposition plus adaptées au traitement efficace de problèmes définis sur des modèles graphiques en s'appuyant sur l'expérience acquise avec les décompositions arborescentes.

(2) Compte tenu des algorithmes de traitement, l'objectif est d'exploiter efficacement les différentes techniques de décomposition de graphes qui ont été développées par la communauté mathématique pour aboutir à des algorithmes plus efficaces en temps et ou en espace.

(3) Sur un plan plus pratique, l'objectif est de repousser les limites de calcul des approches de décomposition existantes pour traiter efficacement des problèmes à la fois plus grands et plus difficiles. Cela se fera via l'extension de la plateforme de traitement de modèles graphiques « toulbar2 » et le transfert de ces résultats vers les domaines d’application déjà identifiés et vers d'autres domaines de l'optimisation combinatoire.