Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-540-85958-1_34
Title: Maintaining generalized arc consistency on ad hoc r-ary constraints
Authors: Cheng, K.C.K.
Yap, R.H.C. 
Issue Date: 2008
Source: Cheng, K.C.K.,Yap, R.H.C. (2008). Maintaining generalized arc consistency on ad hoc r-ary constraints. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5202 LNCS : 509-523. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-540-85958-1_34
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.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/41587
ISBN: 3540859578
ISSN: 03029743
DOI: 10.1007/978-3-540-85958-1_34
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

24
checked on Dec 5, 2017

Page view(s)

86
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.