Skip to Main content Skip to Navigation
Conference papers

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

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00291564
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 2:45:11 PM
Last modification on : Wednesday, June 2, 2021 - 11:00:32 AM
Long-term archiving on: : Friday, May 28, 2010 - 10:55:34 PM

File

pages-173-179-article44.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291564, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

192

Files downloads

422