Optimisation de la recherche combinatoire d'un solveur mêlant programmation par contrainte et belief propagation

La programmation par contraintes est une méthode populaire pour résoudre les problèmes combinatoires. Cette popularité est en grande partie due à sa capacité à exploiter les contraintes pour accélérer fortement la résolution. En effet, les contraintes lui permettent de filtrer les valeurs impossibles au fur et à mesure de la recherche de solution, réduisant ainsi fortement l'espace de recherche. Mais l'amplitude de ce filtrage est fortement impactée par l'ordre dans lequel les variables sont fixées. Pour cette raison, les heuristiques d'ordonnancement de variables robustes et généralisables sont un enjeu crucial pour la programmation par contraintes. L'ajout de la propagation de croyances à un solveur de programmation par contraintes permet de calculer, pour chaque affectation, les distributions marginales. Ces distributions correspondent aux proportions de solutions valides contenant les différentes affectations. Ce sont donc des bases très intéressantes pour une heuristique d'ordonnancement de variables et de valeurs. Le travail présenté dans ce mémoire a pour but d'améliorer l'usage de la propagation de croyances. Nous présentons tout d'abord deux critères d'arrêt dynamiques pour cette propagation. L'idée est de l'arrêter au moment propice afin d'éviter toute itération inutile. Le premier critère observe la stabilité du meilleur marginal présent dans les distributions. Le deuxième observe l'évolution de l'entropie du modèle. De plus, nous présentons aussi deux manières de pondérer les messages envoyés au cours de la propagation. La première est de pondérer en fonction de l'arité des contraintes, tandis que l'autre est basée sur le nombre d'échecs provoqués par chaque contrainte. Enfin, nous présentons trois nouvelles heuristiques : minentropy, choisissant de fixer la variable avec la plus faible entropie, impact-entropy qui choisit les variables à fixer de manière à réduire le plus fortement possible l'entropie du modèle et une combinaison de ces deux heuristiques nommée impact-min-entropy. Nous avons testé nos contributions sur 1474 exemplaires parmi 11 problèmes différents. Les résultats montrent que nos critères d'arrêt dynamiques pour la propagation de croyance sont effectivement capables d'induire une réduction du temps de calcul. De plus, nos schémas de pondération améliorent significativement les performances de notre approche pour certains problèmes. Enfin, nos expériences démontrent que l'heuristique min-entropy est une meilleure exploitation des distributions marginales que les autres heuristiques les utilisant. Elle est de plus compétitive avec l'heuristique de l'état de l'art dom/wdeg.