SODA

Maintaining Generalized Arc Consistency on Ad-hoc n-ary Boolean Constraints

Cheng, Kenil C. K. and Yap, Roland H.C. (2006) Maintaining Generalized Arc Consistency on Ad-hoc n-ary Boolean Constraints. [SICS Report]

[img]
Preview
PDF
249Kb
[img]Postscript
478Kb

Abstract

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.

Item Type:SICS Report
Uncontrolled Keywords:constraint programming, CSP, BDD, generalized arc consistency
ID Code:2304
Deposited By:Vicki Carleson
Deposited On:29 Oct 2007
Last Modified:18 Nov 2009 16:05

Repository Staff Only: item control page