Olivier Lhomme, Jean-Charles Regin
The GAC-Scheme has become a popular general purpose algorithm for solving n-ary constraints, although it may scan an exponential number of supporting tuples. In this paper, we develop a major improvement of this scheme. When searching for a support, our new algorithm is able to skip over a number of tuples exponential in the arity of the constraint by exploiting knowledge about the current domains of the variables. We demonstrate the effectiveness of the method for large table constraints.
Content Area: 6. Constraint Satisfaction and Satisfiability
Subjects: 15.2 Constraint Satisfaction
Submitted: May 10, 2005