Skip to Main content Skip to Navigation
Conference papers

Solving Difficult CSPs with Relational Neighborhood Consistency

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 : Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) as a strong local consistency property for binary CSPs. While enforcing NIC can significantly filter the variables domains, the proposed algorithm is too costly to be used on dense graphs or for lookahead during search. In this paper, we introduce and characterize Relational Neighborhood Inverse Consistency (RNIC) as a local consistency property that operates on the dual graph of a non-binary CSP. We de- scribe and characterize a practical algorithm for enforcing it. We argue that defining RNIC on the dual graph unveils unsuspected opportunities to reduce the computational cost of our algorithm and increase its filtering effectiveness. We show how to achieve those effects by modifying the topology of the dual graph, yielding new variations the RNIC property. We also introduce an adaptive strategy to automatically select the appro- priate property to enforce given the connectivity of the dual graph. We integrate the resulting techniques as full lookahead strategies in a backtrack search procedure for solving CSPs, and demonstrate the effectiveness of our approach for solving known difficult benchmark problems.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00748656
Contributor : Joël Quinqueton <>
Submitted on : Monday, November 5, 2012 - 5:05:21 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Long-term archiving on: : Wednesday, February 6, 2013 - 3:56:20 AM

File

aaai11.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00748656, version 1

Collections

Citation

Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessière. Solving Difficult CSPs with Relational Neighborhood Consistency. AAAI Conference on Artificial Intelligence, Aug 2011, San Francisco, CA, United States. pp.112-119. ⟨lirmm-00748656⟩

Share

Metrics

Record views

270

Files downloads

425