Skip to Main content Skip to Navigation
Conference papers

Cycle-Based Singleton Local Consistencies

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

Cited literature [9 references]  Display  Hide  Download
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Thursday, October 18, 2018 - 11:06:43 AM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM
Long-term archiving on: : Saturday, January 19, 2019 - 1:22:13 PM


Publisher files allowed on an open archive


  • HAL Id : lirmm-01711585, version 1



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



Record views


Files downloads