Intermediate Consistencies by Delaying Expensive Propagators

Andreï Legtchenko, Arnaud Lallouet, and AbdelAli Ed-Dbali

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.