Résumé
Les problèmes sur-contraints ont été largement étudiés dans les années 90, et notamment les algorithmes de résolution de Max-CSP [Freuder et Wallace, 1992; Wallace, 1994; Verfaillie et al. , 1996; Affane et Bennaceur, 1998; Larrosa et al. , 1999]. Le principe commun à ces algorithmes est de calculer une borne inférieure du nombre de contraintes violées. Ils n'exploitent pas de mécanisme de propagation. Aussi, afin d'améliorer la résolution, des travaux récents visent à pallier ce défaut. Les algorithmes de "Soft Arc-Consistency" propagent des compteurs d'inconsistance [Larrosa, 2002; Schiex, 2000; 2002]. Une autre technique consisteà utiliser les algorithmes de filtrage des contraintes et la propagation afin d'iden tifier des ensembles de contraintes en conflit, appelés conflict-sets, qui sont disjoints les uns des autres [Régin et al. , 2001] ; le nombre de conflict-sets extraits est une borne inférieure. Dans cet article, nous plaçons cette technique dans un cadre plus général. Nous montrons qu'elle correspond à un cas polynomial d'un problème NP-Complet (Hit-ting Set). Nous présentons un deuxième cas polynomial où les conflict-sets peuvent avoir des contraintes en commun, et un troisième cas qui n'est pas polynomial mais tel que l'on puisse approximer le résultat polynomialement. Dans chaque cas nous fournissons l'algorithme de calcul de la borne inférieure et un schéma pour générer incrémentalement la collection de conflict-sets. Nous discutons des extensions de ce travail aux problèmatiques où l'on doit maintenir une borne inférieure calculée à partir de données non disjointes.