On Neighborhood Singleton Consistencies
On Neighborhood Singleton Consistencies
Anastasia Paparrizou, Kostas Stergiou
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 736-742.
https://doi.org/10.24963/ijcai.2017/102
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.
Keywords:
Constraints and Satisfiability: Constraint Satisfaction
Constraints and Satisfiability: Evaluation and Analysis