Abstract:
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.

Published Date: May 2004
Registration: ISBN 978-1-57735-201-3
Copyright: Published by The AAAI Press, Menlo Park, California.