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 language | English |
---|---|
Title of host publication | Principles and Practice of Constraint Programming – CP 2004 |
Subtitle of host publication | 10th International Conference, CP 2004 Toronto, Canada, September 27 - October 1, 2004 Proceedings |
Editors | Mark Wallace |
Place of Publication | Berlin Germany |
Publisher | Springer |
Pages | 347-361 |
Number of pages | 15 |
ISBN (Print) | 3540232419 |
DOIs | |
Publication status | Published - 1 Dec 2004 |
Externally published | Yes |
Event | International Conference on Principles and Practice of Constraint Programming 2004 - Toronto, Canada Duration: 27 Sept 2004 → 1 Oct 2004 Conference number: 10th |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 3258 |
ISSN (Print) | 0302-9743 |
Conference
Conference | International Conference on Principles and Practice of Constraint Programming 2004 |
---|---|
Abbreviated title | CP 2004 |
Country/Territory | Canada |
City | Toronto |
Period | 27/09/04 → 1/10/04 |