Data Structures for Generalised Arc Consistency for Extensional Constraints

Ian P. Gent, Chris Jefferson, Ian Miguel, Peter Nightingale

Extensional (table) constraints are an important tool for attacking combinatorial problems with constraint programming. Recently there has been renewed interest in fast propagation algorithms for these constraints. We describe the use of two alternative data structures for maintaining generalised arc consistency on extensional constraints. The first, the Next-Difference list, is novel and has been developed with this application in mind. The second, the trie, is well known but its use in this context is novel. Empirical analyses demonstrate the efficiency of the resulting approaches, both in GAC-schema, and in the watched-literal table constraint in Minion.

Subjects: 15.2 Constraint Satisfaction; 15.7 Search

Submitted: Apr 24, 2007

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.