Please use this identifier to cite or link to this item:
Title: An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints
Authors: Cheng, K.C.K.
Yap, R.H.C. 
Keywords: Ad hoc constraint
Generalized arc consistency
Global constraint
Multi-valued decision diagram
Negative constraint
Positive constraint
Table constraint
Issue Date: 2010
Citation: Cheng, K.C.K., Yap, R.H.C. (2010). An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints 15 (2) : 265-304. ScholarBank@NUS Repository.
Abstract: A table constraint is explicitly represented as its set of solutions or non-solutions. This ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC expensive. In this paper, we address the space and time inefficiencies simultaneously by presenting the mddc constraint. mddc is a global constraint that represents its (non-)solutions with a multi-valued decision diagram (MDD). The MDD-based representation has the advantage that it can be exponentially smaller than a table. The associated GAC algorithm (called mddc) has time complexity linear to the size of the MDD, and achieves full incrementality in constant time. In addition, we show how to convert a positive or negative table constraint into an mddc constraint in time linear to the size of the table. Our experiments on structured problems, car sequencing and still-life, show that mddc is also a fast GAC algorithm for some global constraints such as sequence and regular. We also show that mddc is faster than the state-of-the-art generic GAC algorithms in Gent et al. (2007), Lecoutre and Szymanek (2006), Lhomme and Régin (2005) for table constraint. © Springer Science+Business Media, LLC 2009.
Source Title: Constraints
ISSN: 13837133
DOI: 10.1007/s10601-009-9087-y
Appears in Collections:Staff Publications

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


checked on Jan 17, 2020


checked on Jan 10, 2020

Page view(s)

checked on Dec 30, 2019

Google ScholarTM



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