Maintaining Generalized Arc Consistency on Ad-hoc n-ary Boolean Constraints
Number of Authors: 2
2006 (English)Report (Refereed)
Binary decision diagrams (BDDs) can compactly represent ad-hoc n-ary Boolean constraints. However, there is no generalized arc consistency (GAC) algorithm which exploit BDDs. For example, the global case constraint by SICStus Prolog for ad-hoc constraints is designed for non-Boolean domains. In this paper, we introduce a new GAC algorithm, bddc, for BDD constraints. Our empirical results demonstrate the advantages of a new BDD-based global constraint -- bddc is more efficient both in terms of memory and time than the case constraint when dealing with ad-hoc Boolean constraints. This becomes important as the size of the ad-hoc constraints becomes large.
Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 2006, 1. , 6 p.
SICS Technical Report, ISSN 1100-3154 ; 2006:12
constraint programming, CSP, BDD, generalized arc consistency
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-22026OAI: oai:DiVA.org:ri-22026DiVA: diva2:1041568