Skip to Main content Skip to Navigation
Conference papers

Détection de Conflits pour la Résolution de Problèmes Sur-Contraints

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269779
Contributor : Christine Carvalho de Matos <>
Submitted on : Friday, October 11, 2019 - 3:00:14 PM
Last modification on : Thursday, June 25, 2020 - 3:04:41 AM

File

jnpc03-conflicts.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00269779, version 1

Citation

Thierry Petit, Christian Bessière, Jean-Charles Régin. Détection de Conflits pour la Résolution de Problèmes Sur-Contraints. JNPC: Journées Nationales sur la Résolution Pratique des Problèmes NP-Complets, Jun 2003, Amiens, France. pp.293-307. ⟨lirmm-00269779⟩

Share

Metrics

Record views

150

Files downloads

84