Please use this identifier to cite or link to this item:
|Title:||Maintaining generalized arc consistency on ad hoc r-ary constraints|
|Citation:||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 , 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)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 17, 2018
checked on Nov 24, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.