Quick Shaving

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.

Authors

• Olivier Lhomme Jean-Charles Regin

Keywords

No keywords are indexed for this paper.