Détection de Conflits pour la Résolution de Problèmes Sur-Contraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2003

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

Abstract

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.
Fichier principal
Vignette du fichier
jnpc03-conflicts.pdf (19.66 Mo) Télécharger le fichier
Origin Publisher files allowed on an open archive
Loading...

Dates and versions

lirmm-00269779 , version 1 (11-10-2019)

Identifiers

  • HAL Id : lirmm-00269779 , version 1

Cite

Thierry Petit, Christian Bessiere, 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⟩
432 View
25 Download

Share

Gmail Mastodon Facebook X LinkedIn More