Intermediate Consistencies by Delaying Expensive Propagators

What makes a good consistency? Depending on the constraint, it may be a good pruning power or a low computational cost. By “weakening” arc-consistency, we propose to define new automatically generated solvers which form a sequence of consistencies weaker than arc-consistency. The method presented in this paper exploits a form of regularity in the cloud of constraint solutions: the density of solution orthogonal to a projection. This approach is illustrated on the sparse constraints “to be a n-letters english word” and crossword CSPs, where interesting speed-ups are obtained.