Improvement and Integration of Counting-Based Search Heuristics in Constraint Programming

Ce mémoire s'intéresse à la programmation par contraintes, un paradigme pour résoudre des problèmes combinatoires. Pour la plupart des problèmes, trouver une solution n'est pas possible si on se limite à des mécanismes d'inférence logique; l'exploration d'un espace des solutions à l'aide d'heuristiques de recherche est nécessaire. Des nombreuses heuristiques existantes, les heuristiques de branchement basées sur le dénombrement seront au centre de ce mémoire. Cette approche repose sur l'utilisation d'algorithmes pour estimer le nombre de solutions des contraintes individuelles d'un problème de satisfaction de contraintes. Notre contribution se résume principalement à l'amélioration de deux algorithmes de dénombrement pour les contraintes alldifferent et spanningTree; ces contraintes peuvent exprimer de nombreux problèmes de satisfaction, et sont par le fait même essentielles à nos heuristiques de branchement. Notre travail fait également l'objet d'une contribution à un solveur de programmation par contraintes open-source. Ainsi, l'ensemble de ce mémoire est motivé par cette considération pratique; nos algorithmes doivent être accessibles et performants. Finalement, nous explorons deux techniques applicables à l'ensemble de nos heuristiques: une technique qui réutilise des calculs précédemment faits dans l'arbre de recherche ainsi qu'une manière d'apprendre de nouvelles heuristiques de branchement pour un problème.=