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.

Abstract

Constraint Programming is a popular method to solve combinatorial problems. This popularity is mostly due to its capacity to exploit constraints in order to strongly reduce the runtime. Indeed, constraints allow to filter impossible values through the search of a solution, strongly reducing the search space. But the amplitude of this filtering is strongly impacted by the order in which variables are fixed. Therefore, robust and generalizable variable ordering heuristics are a major issue in Constraint Programming. By adding belief propagation to a Constraint Programming solver, it is possible to compute marginal distributions for each assignment. Those distributions represent the proportion of valid solutions that contain the assignments. Therefore they can be very interesting tools for variable and value ordering heuristics. The work presented in this thesis aims to improve the use of belief propagation. First, we present two dynamic stopping criteria for this propagation. The goal is to stop it at the best moment in order to avoid any useless iteration. The first criterion looks at the stability of the best marginal of all distributions. The second one looks at the variation of the model's entropy. We also present two ways to weight messages during belief propagation. The first one is to weight based on the arity of constraints, the second one uses the number of conflicts created by each constraint. Finally, we present three new variable ordering heuristics : min-entropy, which fixes the variables with the lowest entropy, impact-entropy, which fixes variables that are supposed to have the strongest impact on the model's entropy, and a combination of these two heuristics named impact-min-entropy. We tested our contributions on 1474 instances from 11 different problems. Results show that our dynamic stopping criteria are able to induce a reduction of runtime. Furthermore our weighing schemes induce a significant improvement of the performance of our approach for several problems. Finally, our experiments show that min-entropy is a better way to exploit marginal distributions than other belief-propagation-based heuristics. Moreover it is competitive with state-of-the-art heuristic dom/wdeg.