Abstract FR:

La programmation par contraintes, carrefour de diverses disciplines, a montre son interet dans de nombreux domaines d'application. De nombreux problemes reels sont dynamiques : le systeme de contraintes les definissant n'est donc pas fige. Pour resoudre un probleme dynamique, il faut assurer une certaine incrementalite et etre capable de traiter les systemes de contraintes contradictoires. En effet, il est souvent indispensable de fournir une solution quitte a ne pas respecter certaines contraintes. On parle alors de relaxation de contraintes. Durant cette these, nous nous sommes interesses a la definition d'un systeme de relaxation de contraintes permettant de maintenir une propriete donnee dans un environnement dynamique. Nous avons mene ces travaux depuis une presentation abstraite d'un tel systeme jusqu'a son implementation. Nous presentons un schema algorithmique general abstrait de la recherche d'une solution a un probleme sur-contraint basee sur l'exploration en meilleur d'abord d'un espace de configurations. Nous en donnons trois instances pour traiter les contraintes lineaires sur les rationnels, les constraint satisfaction problems et les csp numeriques. Les deux dernieres sont definies a l'aide d'un systeme de maintien de deduction dont la maitrise raisonnee nous a permis de donner une implementation de ces instances ayant une bonne complexite : le systeme decorum. Nous montrons, par le biais d'un certain nombre d'experimentations, que l'utilisation de decorum permet de retrouver les resultats classiques sur la transition de phase, de resoudre raisonnablement des problemes de grande taille et d'utiliser la structure du probleme resolu pour ameliorer la recherche. Enfin, nous proposons la contrainte one-of permettant de modeliser et de resoudre une disjonction de contraintes en tirant profit du mecanisme d'exploration de decorum. Nous validons l'interet de la contrainte one-of sur des problemes d'ordonnancement : les open-shop.