Abstract FR:

La résolution de problèmes de satisfaction de contraintes offre, sur le domaine entier, un très large champ d'investigation aussi bien théorique qu'appliqué. La plupart de ces problèmes sont np-complets. Pour les résoudre, de nombreuses méthodes ont été proposées : les méthodes systématiques, la recherche locale, les algorithmes génétiques, la recherche opérationnelle. . . Dans cette thèse, nous décrivons un système de programmation par contraintes spécifique aux domaines finis entiers, SCORE(FD/I) ; qui intègre un langage compilé et une méthode de résolution. Issue de recherches réalisées sur le problème spécifique du placement de n reines sur un échiquier, cette approche a été, depuis, intégrée a un schéma général de programmation par contraintes dont SCORE(FD/I) est une instance dédiée aux entiers. Le langage, déclaratif, statique et de haut niveau, permet de modéliser de manière simple et concise de nombreux problèmes de satisfaction de contraintes et d'optimisation. Le solveur met en oeuvre une méthode de résolution originale, combinant approches systématique et locale afin de profiter des avantages des deux approches. Le caractère systématique de la méthode assure sa complétude. Les critères issus de la recherche locale permettent de prendre en compte certaines propriétés globales du problème. Les objectifs de ces travaux visent principalement à concevoir un environnement de test pour la résolution de problèmes de contraintes sur des variables entières, à la fois simple d'emploi, proche des concepts de l'utilisateur et efficace. De nombreuses expérimentations ont été réalisées afin d'évaluer les performances du système et particulièrement, les heuristiques mises en oeuvres dans la méthode de résolution. Enfin, deux applications concrètes ont permis de valider notre système : le problème de carsequencing et l'intégration de schémas logiques dans des fpgas.