Revisiting Neighborhood Inverse Consistency on Binary CSPs

Robert J. Woodward 1 Shant Karakashian 1 Berthe Y. Choueiry 1 Christian Bessière 2
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Our goal is to investigate the definition and application of strong consistency properties on the dual graphs of binary Constraint Satisfaction Problems (CSPs). As a first step in that direction, we study the structure of the dual graph of binary CSPs, and show how it can be arranged in a triangle-shaped grid. We then study, in this context, Relational Neighborhood Inverse Consistency (RNIC), which is a con- sistency property that we had introduced for non-binary CSPs. We discuss how the structure of the dual graph of binary CSPs affects the consistency level enforced by RNIC. Then, we compare, both theoreti- cally and empirically, RNIC to Neighborhood Inverse Consistency (NIC) and strong Conservative Dual Consistency (sCDC), which are higher- level consistency properties useful for solving difficult problem instances. We show that all three properties are pairwise incomparable.
Type de document :
Communication dans un congrès
CP: Principles and Practice of Constraint Programming, Oct 2012, Québec City, Canada. 18th International Conference on Principles and Practice of Constraint Programming, pp.688-703, 2012, 〈http://archive.a4cp.org/cp2012/〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00748179
Contributeur : Joël Quinqueton <>
Soumis le : lundi 5 novembre 2012 - 09:31:56
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : mercredi 6 février 2013 - 03:53:50

Fichier

cp12-rnic.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00748179, version 1

Collections

Citation

Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessière. Revisiting Neighborhood Inverse Consistency on Binary CSPs. CP: Principles and Practice of Constraint Programming, Oct 2012, Québec City, Canada. 18th International Conference on Principles and Practice of Constraint Programming, pp.688-703, 2012, 〈http://archive.a4cp.org/cp2012/〉. 〈lirmm-00748179〉

Partager

Métriques

Consultations de la notice

202

Téléchargements de fichiers

261