Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10601-009-9087-y
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
Source: 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. https://doi.org/10.1007/s10601-009-9087-y
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40290
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.

SCOPUSTM   
Citations

53
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

22
checked on Nov 18, 2017

Page view(s)

93
checked on Dec 17, 2017

Google ScholarTM

Check

Altmetric


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