Une nouvelle approche pour le test d'inconsistance de CSP

Résumé : Tester la consistance de CSP est en théorie un problème NP-Complet. Il existe deux familles de méthodes pour le test de consistance. La première famille regroupe les méthodes complètes qui font un parcours exhaustif de l'espace de recherche de solutions. Ces méthodes ont l'avantage de prouver l'inconsistance de CSP, cependant leur complexité croît exponentiellement avec la taille du problème. La seconde famille inclut les méthodes incomplètes qui font de la recherche locale sur l'espace de recherche de solutions. Ces méthodes ont été utilisées efficacement pour trouver des solutions pour des problèmes de grande taille que les méthodes complètes ne peuvent résoudre. Le principal inconvénient des méthodes incomplètes reste tout de même leur incapacité de prouver l'inconsistance d'une instance CSP. L'un des challenges mis en avant par la communauté CP (Selman et al. 1997) est de proposer des méthodes incomplètes efficaces pour la preuve d'inconsistance de CSP. Le travail que nous présentons ici est une contribution à ce difficile challenge. Nous introduisons une nouvelle méthode incomplète pour le test d'inconsistance qui se base sur la notion de dominance entre CSPs et la coloration de la micro-structure du CSP. Nous avons expérimenté la méthode sur des instances CSP générées aléatoirement et les résultats obtenus sont très encourageant.