La redondance dans les CSPs

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.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.173-179, 2008
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00291564
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 14:45:11
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : vendredi 28 mai 2010 - 22:55:34

Fichier

pages-173-179-article44.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291564, version 1

Collections

Citation

Assef Chmeiss, Vincent Krawczyk, Lakhdar Saïs. La redondance dans les CSPs. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.173-179, 2008. 〈inria-00291564〉

Partager

Métriques

Consultations de la notice

132

Téléchargements de fichiers

159