Cycle-Based Singleton Local Consistencies - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2017

Cycle-Based Singleton Local Consistencies


We propose to exploit cycles in the constraint network of a Constraint Satisfaction Problem (CSP) to vehicle constraint propagation and improve the effectiveness of local consistency algorithms. We focus our attention on the consistency property Partition-One Arc-Consistency (POAC), which is a stronger variant of Singleton Arc-Consistency (SAC). We modify the algorithm for enforcing POAC to operate on a minimum cycle basis (MCB) of the incidence graph of the CSP. We empirically show that our approach improves the performance of problem solving and constitutes a novel and effective localization of consistency algorithms. Although this paper focuses on POAC, we believe that exploiting cycles, such as MCBs, is applicable to other consistency algorithms and that our study opens a new direction in the design of consistency algorithms. This research is documented in a technical report (Woordward, Choueiry, and Bessiere 2016).
Fichier principal
Vignette du fichier
14655-66728-1-PB.pdf (597.14 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive

Dates and versions

lirmm-01711585 , version 1 (18-10-2018)


  • HAL Id : lirmm-01711585 , version 1


Robert J. Woodward, Berthe Y. Choueiry, Christian Bessiere. Cycle-Based Singleton Local Consistencies. AAAI Conference on Artificial Intelligence, Feb 2017, San Francisco, United States. pp.5005-5006. ⟨lirmm-01711585⟩
107 View
28 Download


Gmail Mastodon Facebook X LinkedIn More