Solving Difficult CSPs with Relational Neighborhood Consistency - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2011

Solving Difficult CSPs with Relational Neighborhood Consistency

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.
Fichier principal
Vignette du fichier
aaai11.pdf (240.07 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00748656 , version 1 (05-11-2012)

Identifiers

  • HAL Id : lirmm-00748656 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More