Skip to Main content Skip to Navigation
Conference papers

On Neighborhood Singleton Consistencies

Abstract : CP solvers predominantly use arc consistency (AC) as the default propagation method. Many stronger consistencies, such as triangle consistencies (e.g. RPC and maxRPC) exist, but their use is limited despite results showing that they outperform AC on many problems. This is due to the intricacies involved in incorporating them into solvers. On the other hand, singleton consistencies such as SAC can be easily crafted into solvers but they are too expensive. We seek a balance between the efficiency of triangle consistencies and the ease of implementation of singleton ones. Using the recently proposed variant of SAC called Neighborhood SAC as basis, we propose a family of weaker singleton consistencies. We study them theoretically, comparing their pruning power to existing consistencies. We make a detailed experimental study using a very simple algorithm for their implementation. Results demonstrate that they outperform the existing propagation techniques, often by orders of magnitude, on a wide range of problems.
Document type :
Conference papers
Complete list of metadata
Contributor : Fabien Delorme <>
Submitted on : Tuesday, July 27, 2021 - 12:51:48 PM
Last modification on : Thursday, September 9, 2021 - 3:10:21 PM


  • HAL Id : hal-03301106, version 1



Anastasia Paparrizou, Kostas Stergiou. On Neighborhood Singleton Consistencies. 26th International Joint Conference on Artificial Intelligence (IJCAI'17), 2017, Melbourne, Australia. pp.736-742. ⟨hal-03301106⟩



Record views