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 effi-
ciency 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.