Fast set bounds propagation using BDDs

Graeme Gange, Vitaly Lagoon, Peter J. Stuckey

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

4 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
EventEuropean Conference on Artificial Intelligence 2008 - Patras, Greece
Duration: 21 Jul 200825 Jul 2008
Conference number: 18th

Publication series

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

Conference

ConferenceEuropean Conference on Artificial Intelligence 2008
Abbreviated titleECAI 2008
Country/TerritoryGreece
CityPatras
Period21/07/0825/07/08

Cite this