Set bounds and (Split) set domain propagation using ROBDDs

Peter Hawkins, Vitaly Lagoon, Peter J. Stuckey

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

6 Citations (Scopus)


Most propagation-based set constraint solvers approximate the set of possible sets that a variable can take by upper and lower bounds, and perform so-called set bounds propagation. However Lagoon and Stuckey have shown that using reduced ordered binary decision diagrams (ROBDDs) one can create a practical set domain propagator that keeps all information (possibly exponential in size) about the set of possible set values for a set variable. In this paper we first show that we can use the same ROBDD approach to build an efficient bounds propagator. The main advantage of this approach to set bounds propagation is that we need not laboriously determine set bounds propagations rules for each new constraint, they can be computed automatically. In addition we can eliminate intermediate variables, and build stronger set bounds propagators than with the usual approach. We then show how we can combine this with the set domain propagation approach of Lagoon and Stuckey to create a more efficient set domain propagation solver.

Original languageEnglish
Title of host publicationAI 2004: Advances in Artificial Intelligence
Subtitle of host publication17th Australian Joint Conference on Artificial Intelligence Cairns, Australia, December 4-6, 2004 Proceedings
EditorsGeoffrey I. Webb, Xinghuo Yu
Place of PublicationBerlin Germany
Number of pages12
ISBN (Print)3540240594
Publication statusPublished - 1 Dec 2004
Externally publishedYes
EventAustralasian Joint Conference on Artificial Intelligence 2004 - Cairns, Australia
Duration: 4 Dec 20046 Dec 2004
Conference number: 17th (Proceedings)

Publication series

NameLecture Notes in Artificial Intelligence
ISSN (Print)0302-9743


ConferenceAustralasian Joint Conference on Artificial Intelligence 2004
Abbreviated titleAI 2004
Internet address

Cite this