Maintaining generalized arc consistency on ad hoc r-ary constraints

Abstract

In many real-life problems, constraints are explicitly defined as a set of solutions. This ad hoc (table) representation uses exponential memory and makes support checking (for enforcing GAC) difficult. In this paper, we address both problems simultaneously by representing an ad hoc constraint with a multi-valued decision diagram (MDD), a memory efficient data structure that supports fast support search. We explain how to convert a table constraint into an MDD constraint and how to maintain GAC on the MDD constraint. Thanks to a sparse set data structure, our MDD-based GAC algorithm, mddc, achieves full incrementality in constant time. Our experiments on structured problems, car sequencing and still-life, show that mddc is a fast GAC algorithm for ad hoc constraints. It can replace a Boolean sequence constraint [1], and scales up well for structural MDD constraints with 208 variables and 340984 nodes. We also show why it is possible for mddc to be faster than the state-of-the-art generic GAC algorithms in [2,3,4]. Its efficiency on non-structural ad hoc constraints is justified empirically. © 2008 Springer-Verlag Berlin Heidelberg.