Set domain propagation using ROBDDs

Vitaly Lagoon, Peter J. Stuckey

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

15 Citations (Scopus)

Abstract

Propagation based solvers typically represent variables by a current domain of possible values that may be part of a solution. Finite set variables have been considered impractical to represent as a domain of possible values since, for example, a set variable ranging over subsets of {1, . . . , N} has 2N possible values. Hence finite set variables are presently represented by a lower bound set and upper bound set, illustrating all values definitely in (and by negation) all values definitely out. Propagators for finite set variables implement set bounds propagation where these sets are further constrained. In this paper we show that it is possible to represent the domains of finite set variables using reduced ordered binary decision diagrams (ROBDDs) and furthermore we can build efficient domain propagators for set constraints using ROBDDs. We show that set domain propagation is not only feasible, but can solve some problems significantly faster than using set bounds propagation because of the stronger propagation.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming – CP 2004
Subtitle of host publication10th International Conference, CP 2004 Toronto, Canada, September 27 - October 1, 2004 Proceedings
EditorsMark Wallace
Place of PublicationBerlin Germany
PublisherSpringer
Pages347-361
Number of pages15
ISBN (Print)3540232419
DOIs
Publication statusPublished - 1 Dec 2004
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2004 - Toronto, Canada
Duration: 27 Sept 20041 Oct 2004
Conference number: 10th

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3258
ISSN (Print)0302-9743

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2004
Abbreviated titleCP 2004
Country/TerritoryCanada
CityToronto
Period27/09/041/10/04

Cite this