Contributions à la résolution générique des problèmes de satisfaction de contraintes
Institution:
ArtoisDisciplines:
Directors:
Abstract EN:
We propose several techniques aimed to solve the NP-complete Constraint Satisfaction Problem in practice. We distinguish two main approaches: search and inference. We have contributed to improve inference techniques by evolving the central Arc Consistency property. We optimized the best AC algorithms, we studied their behavior on the bounds of the discrete domains, and we finally studied an interesting alternative to Path Consistency: Dual Consistency. This property leads us to design new algorithms that can establish Path Consistency very efficiently. Conservative Dual Consistency is stronger than Conservative Path Consistency, and is much faster to establish. Besides, we have tried to improve MGAC, first by equipping it of Value Ordering Heuristics. We studied how the well known Jeroslow-Wang heuristic, from the SAT problem, would behave if applied to the translation of a CSP problem in SAT. Finally, we studied a hybridization between a local search algorithm based on constraint weighting and MGAC, by exploiting the learning abilities of both algorithms. All techniques developed during this PhD thesis lead to the development of a new API for the Java language, namely CSP4J, able to solve a CSP as part of any Java application. This API is a "black box": as less parameters and expertise are required from a user point of view. A solver based on CSP4J took part in International Solved Competitions with promising results.
Abstract FR:
Nous proposons plusieurs techniques pour résoudre en pratique le problème NP-complet de satisfaction de contraintes de manière générique. Nous distinguons deux grands axes de techniques de résolution de CSP : l'inférence et la recherche. Nous avons contribué à l'amélioration des techniques d'inférence en nous concentrant sur la consistance d'arc : optimisations des algorithmes, comportement de plusieurs algorithmes d'inférence aux bornes de domaines discrets, et enfin une alternative intéressante à la consistance de chemin (PC) : la consistance duale. Cette propriété nous a amenés à concevoir des algorithmes de PC forte très efficaces. La variante conservative de cette consistance est de plus plus forte que la PC conservative, tout en restant plus rapide à établir en pratique. Par ailleurs, nous avons cherché à améliorer MGAC, tout d'abord en l'équipant d'heuristiques de choix de valeurs. En nous basant sur l'heuristique de Jeroslow-Wang, issue du problème SAT, nous montrons comment cette heuristique se comporterait sur un CSP. Enfin, nous propos ons une hybridation entre une recherche locale basée sur la pondération des contraintes et un algorithme MGAC-dom/wdeg, en exploitant les possibilités d'apprentissage de ceux-ci. L'ensemble des techniques développées dans le cadre de cette thèse a amené à la résolution d'une API pour le langage Java, capable de résoudre un CSP au sein d'une application Java quelconque. Cette API a été développée dans l'optique "boîte noire" : le moins de paramètres et d'expertise possibles sont demandés à l'utilisateur. Un prouveur basé sur CSP4J a concouru lors les compétitions internationales de prouveurs CSP avec des résultats encourageants.