Solving NP-hard problems is still a challenge at the theoretical or practical level. This project aims at solving decision, optimization and counting (discrete integration) problems defined as "graphical models" (constraint or cost function networks, bayesian networks, propositional logic and Markov random fields). In such models, a joint function over a set of variables is described as a factorized combination of functions of few variables. This approach is intensively used in artificial intelligence, statistical physics and statistical modeling and the name of "graphical model" underlines the fact that such a factorisation defines an (hyper)graph which vertices are the variables and which (hyper)edges include the variables in each factor. The expressiveness of these models makes them capable of representing a large variety of real problems (in image processing, ressource allocation, planning, bioinformatics, computer music...). However, solving such problems is difficult in terms of theoretical complexity: NP-complete for decision, NP-hard for optimization and #P-complete for counting. This project is more specifically interested in the exploitation of (hyper)graph decomposition techniques applied to the underlying graphs defined by graphical models. Their wide practical interest has been only demonstrated in the last ten years (mostly through the notion of tree decomposition). If their limits are now clear, they also have a great potential for improvement.

Indeed, in the mean time, the community of graph theory has independently produced, a large number of results. Most have however been kept as objects of purely theoretical studies (branch/clique/rank/boolean /matching/modular/treecut/tree-depth-decompositions just to name a few). Today, theoretical results on these decompositions have not yet been exploited to improve graphical model processing algorithms or, a fortiori, effective operational processing systems. This is not surprising since most of these results have been studied for theoretical reasons, without the explicit objective of solving graphical models in practise. This type of situation is not unusual, the notion of tree-decomposition has been introduced and studied by Roberston and Seymour as a theoretical tool to prove the famous Wagner's conjecture about graph minors. However, this mathematical object has now become a fundamental tool for solving methods which take into account the structure of graphical models.

So, it is clear today that the topic of graph decomposition defines a wide open field of studies that would combine theory, algorithmic results on graphical models and practical solving tools.

The objectives of the project therefore combine these three main axes:

  1. On the theoretical side, the aim is to study existing decompositions or define new decomposition approaches more specifically targeted at effective processing of problems defined on graphical models by also exploiting what has been learnt using tree decompositions.
  2. About processing algorithms, the aim is to effectively exploit the various graph decomposition techniques that have been developped by the mathematical community. This will lead to the development of new algorithms and new heuristics.
  3. On a practical level, the aim is to push the computational frontiers of decomposition approaches to efficiently process problems of increasing hardness and size. This will be possible by extending the graphical model processing platform "toulbar2" and transferring these results towards already identified applied fields and other approaches to combinatorial optimization.

Globally, by aiming at the design of new theoretical and algorithmical results targeted to real problems expressed as queries on graphical models together with actual implementation of processing tools that will be applied to challenging real world problems, and given the large existing gap between theory and practise in the field, this project has the capacity to have a strong impact, both on the theoretical and practical side.

Keywords: Artificial intelligence, Decomposition


Résoudre des problèmes NP-difficiles demeure encore un challenge tant au niveau théorique qu'au niveau pratique. Ce projet vise à résoudre des problèmes de décision, d'optimisation et de dénombrement (intégration discrète) vus comme des modèles graphiques (réseaux de contraintes ou de fonctions de coût, réseaux bayésiens, logique propositionnelle, champs aléatoires de Markov). Dans de tels modèles, une fonction portant sur un ensemble des variables est décrite comme une combinaison de fonctions portant sur quelques variables. Cette approche est exploitée intensivement en intelligence artificielle, en physique statistique et en modélisation statistique. Le nom de "modèles graphiques" souligne le fait qu'une telle factorisation définit un (hyper)graphe dont les sommets correspondent aux variables et les (hyper)arêtes incluent les variables de chaque facteur. L'expressivité de ces modèles leur permet de représenter une large variété de problèmes réels (en traitement d'images, en allocation de ressource, en planification, en bio-informatique, en informatique musicale, ...). Cependant, résoudre de tels problèmes s'avère difficile en termes de complexité théorique : NP-complets pour la décision, NP-difficiles pour l'optimisation et #P-complets pour le dénombrement. Ce projet s'intéresse plus spécifiquement à l'exploitation des techniques de décompositions d'(hyper)graphes appliquées aux graphes sous-jacents définis par les modèles graphiques. Leur grand intérêt pratique a seulement été démontré ces dix dernières années (principalement grâce à la notion de décomposition arborescente). Si leurs limites sont maintenant claires, elles possèdent un grand potentiel d'amélioration.

En effet, dans le même temps, la communauté de la théorie des graphes a indépendamment produit de très nombreux résultats. Cependant, la plupart consiste essentiellement en des objets d'études purement théoriques (comme, par exemple, les branch/clique/rank/boolean/matching/modular/treecut/tree-depth décompositions). Aujourd'hui, les résultats théoriques sur ces décompositions n'ont pas encore été exploités pour améliorer les algorithmes de traitement des modèles graphiques, ou, a fortiori, les systèmes de traitement opérationnel efficaces. Ce n'est pas surprenant puisque la plupart de ces résultats ont été établis pour des raisons théoriques, sans chercher explicitement à résoudre des modèles graphiques en pratique. Ce type de situation n'est pas rare, la notion de décomposition arborescente a été introduite et étudiée par Roberston et Seymour comme un outil théorique pour démontrer la fameuse conjecture de Wagner concernant les mineurs de graphes. Toutefois, cet objet mathématique est devenu maintenant un outil fondamental pour les méthodes de résolution qui prennent en compte la structure des modèles graphiques. Par conséquent, il est clair aujourd'hui que le thème des décompositions de graphes définit un vaste domaine d'études qui combine la théorie, les résultats algorithmiques sur les modèles graphiques et les outils pratiques de résolution.

Les objectifs du projet combinent donc ces trois axes principaux :

  1. Du côté théorique, le but est d'étudier les décompositions existantes ou de définir de nouvelles approches par décomposition afin d'aboutir à un traitement efficace des problèmes définis par des modèles graphiques visant plus spécifiquement à résoudre en exploitant également tout ce qui a été appris de l'usage des décompositions arborescentes.
  2. Concernant les algorithmes de traitement, l'objectif est d'exploiter effectivement les différentes techniques de décompositions de graphes qui ont été développés par la communauté mathématique. Cela conduira au développement de nouveaux algorithmes et de nouvelles heuristiques.
  3. Sur un plan pratique, le but est de repousser les frontières algorithmiques des approches par décomposition afin de résoudre efficacement des problèmes d'une difficulté et d'une taille croissantes. Cela peut passer par une extension des modèles graphiques exploités par la plateforme "toulbar2" et transférer ces résultats vers des champs d'applications déjà identifiés et d'autres approches d'optimisation combinatoire.

Globalement, en visant la conception de nouveaux résultats théoriques et algorithmiques ciblés vers des problèmes réels exprimés comme des requêtes sur des modèles graphiques ainsi que la mise en œuvre effective d'outils de traitement, qui seront appliqués sur des problèmes réels difficiles, et compte tenu du large fossé existant entre théorie et pratique dans cette thématique, ce projet a la capacité d'avoir un impact fort sur les aspects à la fois théoriques et pratiques.

Mots-clés : Intelligence artificielle, Décomposition