Note publique d'information : 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.
paprika.idref.fr
data.idref.fr
Documentation
