La redondance dans les CSPs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

La redondance dans les CSPs

Assef Chmeiss
Lakhdar Saïs

Résumé

Dans ce papier, une nouvelle technique pour calculer des sous-ensembles irredondant de réseaux de contraintes est proposé. La vérification d'une contrainte donnée est connue pour être Co-NP complet. Dans notre approche, différentes consistances locales polynomiales sont utilisées pour réduire la complexité. Le réseau de contraintes obtenu est irredondant modulo une consistance locale donnée. Notre principal objectif est de mesurer les relations entre la redondance des contraintes et l'efficacité des solveurs CSP. Plus précisément, les contraintes redondantes sont éliminées de l'instance d'origine produisant un problème équivalent par rapport à la satisfiabilité. Notre approche admet des particularités intéressantes. Premièrement, l'élimination de contraintes redondantes peut aider le solveur CSP à diriger la recherche vers la partie la plus contrainte du réseau. Deuxièmement, une telle élimination peut conduire à améliorer le comportement des heuristiques de choix de variables et à réduire le nombre de vérification de contraintes. De façon intéressante, notre approche peut être utilisée pour mesurer le degré de redondance des contraintes des instances CSPs. Les résultats expérimentaux sur les instances prises de la dernière compétition CSP montre clairement l'intérêt de l'approche que nous proposons.
Fichier principal
Vignette du fichier
pages-173-179-article44.pdf (223.33 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00291564 , version 1 (27-06-2008)

Identifiants

  • HAL Id : inria-00291564 , version 1

Citer

Assef Chmeiss, Vincent Krawczyk, Lakhdar Saïs. La redondance dans les CSPs. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.173-179. ⟨inria-00291564⟩
87 Consultations
381 Téléchargements

Partager

Gmail Facebook X LinkedIn More