Fast set bounds propagation using BDDs

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

Abstract

Set bounds propagation is the most popular approach to solving constraint satisfaction problems (CSPs) involving set variables. The use of reduced ordered Binary Decision Diagrams (BDDs) to represent and solve set CSPs is well understood and brings the advantage that propagators for arbitrary set constraints can be built. This can substantially improve solving. The disadvantages of BDDs is that creating and manipulating BDDs can be expensive. In this paper we show how we can perform set bounds propagation using BDDs in a much more efficient manner by generically creating set constraint predicates, and using a marking approach to propagation. The resulting system can be significantly faster than competing approaches to set bounds propagation.

Original languageEnglish
Title of host publicationFrontiers in Artificial Intelligence and Applications
PublisherIOS Press
Pages505-509
Number of pages5
ISBN (Print)978158603891
DOIs
Publication statusPublished - 1 Jan 2008
Externally publishedYes
Event18th European Conference on Artificial Intelligence, ECAI 2008 - Patras, Greece
Duration: 21 Jul 200825 Jul 2008

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume178
ISSN (Print)0922-6389

Conference

Conference18th European Conference on Artificial Intelligence, ECAI 2008
CountryGreece
CityPatras
Period21/07/0825/07/08

Cite this

Gange, G., Lagoon, V., & Stuckey, P. J. (2008). Fast set bounds propagation using BDDs. In Frontiers in Artificial Intelligence and Applications (pp. 505-509). (Frontiers in Artificial Intelligence and Applications; Vol. 178). IOS Press. https://doi.org/10.3233/978-1-58603-891-5-505