Soutenance de thèse de NABIL ADRAR

Cette thèse s'inscrit dans le cadre de la programmation par contraintes, et porte sur l'étude et le traitement par décomposition structurelle des réseaux de contraintes au sens des problèmes de satisfaction de contraintes (CSP). Dans la première partie, nous traitons le calcul d'hypergraphes partiels dont la largeur (au sens de la décomposition arborescente) est bornée par une constante entière. Il s'agit, étant donné un hypergraphe $H = (V, E)$ et un entier $k$, de trouver un hypergraphe partiel $H' = (V, E') (E' subseteq E)$ tel que la largeur (au sens de la emph{treewidth}) de sa $2$-section ou emph{graphe primal} est au plus $k - 1$. Cette question originellement issue d'une approche de filtrage de CSP basée sur la structure trouve également un intérêt dans le cadre plus général des modèles graphiques (réseaux bayésiens, réseaux de fonctions de coût, champs aléatoires de Markov, etc). Nous proposons un algorithme de complexité polynomiale sans garantie d'optimalité, mais qui permet néanmoins de calculer l'optimum dans certains cas (dont celui des hypergraphes $alpha$-acycliques). La proximité fréquente de l'optimum est par ailleurs validée par les évaluations expérimentales que nous avons menées. Il s'avère cependant que son exploitation pour l'approche de filtrage qui avait motivé cette étude est beaucoup moins probante sur un plan expérimental. En deuxième partie, nous proposons une nouvelle approche de calcul de décompositions arborescentes d'hypergraphes. Cette approche fait évoluer, en cours de calcul, une décomposition arborescente en ajoutant progressivement les hyperarêtes de l'hypergraphe considéré, au moyen d'une heuristique de choix d'hyperarête, jusqu'à obtenir une décomposition arborescente finale globale de l'hypergrahe en entrée. Cette approche recèle potentiellement deux vertus. Tout d'abord, elle permet la prise en compte de nouvelles hyperarêtes au sein de la décomposition arborescente associée sans devoir recalculer à nouveau une nouvelle décomposition arborescente. En outre, cette approche permet potentiellement de mieux gérer certains paramètres qui sont cruciaux pour la résolution de CSP, comme notamment la taille des séparateurs entre clusters, ce qui constitue un réel avantage par rapport à des approches heuristiques telles que des méthodes de l'état de l'art comme emph{Min-Fill} ou emph{MCS}. Cette nouvelle approche est évaluée expérimentalement au regard des paramètres utiles pour son exploitation pour la résolution de CSPs. La troisième partie de ce manuscrit porte sur la prise en compte des contraintes globales par des approches de résolution fondées sur la décomposition. S'il est maintenant admis que les contraintes globales constituent un outil quasiment incontournable dans la cadre de la modélisation puis de la résolution de problèmes en termes de contraintes, leur traitement via des approches fondées sur la décomposition constitue un réel défi pour la communauté. En effet, leur intégration dans les réseaux de contraintes engendre généralement une dégradation rédhibitoire de la largeur et donc des garanties en termes de bornes de complexité par les méthodes de résolution par décomposition. Pour contourner cette difficulté, nous étudions cette question par une approche fondée sur la réécriture de ces contraintes globales de sorte à conserver leur sémantique, tout en limitant l'accroissement de la larguer induite. Cette approche devrait rendre admissible des traitements par décomposition. Enfin, nous fournissons une évaluation expérimentale de cette nouvelle approche.

This thesis falls within the framework of constraint programming, and deals with the study and structural decomposition processing of constraint networks in the sense of constraint satisfaction problems (CSP). In the first part, we deal with the computation of partial hypergraphs whose width (in the sense of tree decomposition) is bounded by an integer constant. Given a hypergraph $H = (V, E)$ and an integer $k$, find a partial hypergraph $H' = (V, E') (E' subseteq E)$ such that the width (in the sense of emph{treewidth}) of its $2$-section or emph{primal graph} is at most $k - 1$. This question, which originally arose from a structure-based CSP filtering approach, is also of interest in the more general context of graphical models (Bayesian networks, cost function networks, Markov random fields, etc.). We propose a polynomial-complexity algorithm with no guarantee of optimality, but which can nevertheless be used to compute the optimum in certain cases (including $alpha$-acyclic hypergraphs). The frequent proximity of the optimum is also validated by the experimental evaluations we have carried out. It turns out, however, that its exploitation for the filtering approach that motivated this study is much less convincing experimentally. In the second part, we propose a new approach to calculating tree decompositions of hypergraphs. This approach evolves a tree decomposition during computation by progressively adding hyperedges of the hypergraph under consideration, by means of a hyperedge selection heuristic, until a final global tree decomposition of the input hypergraph is obtained. This approach has two potential virtues. Firstly, it allows new hyperedges to be taken into account within the associated tree decomposition, without having to recalculate a new tree decomposition. In addition, this approach potentially allows better management of certain parameters that are crucial for solving CSPs, such as the size of separators between clusters, which is a real advantage over heuristic approaches such as state-of-the-art methods like emph{Min-Fill} or emph{MCS}. This new approach is experimentally evaluated with regard to the parameters useful for its exploitation in solving CSPs. The third part of this manuscript deals with the treatment of global constraints by decomposition-based approaches. While it is now accepted that global constraints are an almost indispensable tool for modeling and solving problems in terms of constraints, their treatment via decomposition-based approaches represents a real challenge for the community. Indeed, integrating them into constraint networks generally leads to a prohibitive degradation in width, and therefore in the complexity bounds guaranteed by decomposition-based solution methods. To circumvent this difficulty, we are studying this question using an approach based on rewriting these global constraints in such a way as to preserve their semantics, while limiting the increase in width induced. This approach should make decomposition treatments admissible. Finally, we provide an experimental evaluation of this new approach.