Set domain propagation using ROBDDs

Vitaly Lagoon; Peter J. Stuckey

doi:10.1007/978-3-540-30201-8_27

Set domain propagation using ROBDDs

Vitaly Lagoon, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

13 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 2^N 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	https://doi.org/10.1007/978-3-540-30201-8_27
Publication status	Published - 1 Dec 2004
Externally published	Yes
Event	International Conference on Principles and Practice of Constraint Programming 2004 - Toronto, Canada Duration: 27 Sep 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	Canada
City	Toronto
Period	27/09/04 → 1/10/04

Access to Document

10.1007/978-3-540-30201-8_27

Link to publication in Scopus

Cite this

Lagoon, V., & Stuckey, P. J. (2004). Set domain propagation using ROBDDs. In M. Wallace (Ed.), Principles and Practice of Constraint Programming – CP 2004: 10th International Conference, CP 2004 Toronto, Canada, September 27 - October 1, 2004 Proceedings (pp. 347-361). (Lecture Notes in Computer Science; Vol. 3258). Springer. https://doi.org/10.1007/978-3-540-30201-8_27

@inproceedings{e1998af9fb3243b9a7780f5d8bb44edd,

title = "Set domain propagation using ROBDDs",

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.",

author = "Vitaly Lagoon and Stuckey, {Peter J.}",

year = "2004",

month = dec,

day = "1",

doi = "10.1007/978-3-540-30201-8_27",

language = "English",

isbn = "3540232419",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "347--361",

editor = "Mark Wallace",

booktitle = "Principles and Practice of Constraint Programming – CP 2004",

note = "International Conference on Principles and Practice of Constraint Programming 2004, CP 2004 ; Conference date: 27-09-2004 Through 01-10-2004",

}

Lagoon, V & Stuckey, PJ 2004, Set domain propagation using ROBDDs. in M Wallace (ed.), Principles and Practice of Constraint Programming – CP 2004: 10th International Conference, CP 2004 Toronto, Canada, September 27 - October 1, 2004 Proceedings. Lecture Notes in Computer Science, vol. 3258, Springer, Berlin Germany, pp. 347-361, International Conference on Principles and Practice of Constraint Programming 2004, Toronto, Canada, 27/09/04. https://doi.org/10.1007/978-3-540-30201-8_27

Set domain propagation using ROBDDs. / Lagoon, Vitaly; Stuckey, Peter J.

Principles and Practice of Constraint Programming – CP 2004: 10th International Conference, CP 2004 Toronto, Canada, September 27 - October 1, 2004 Proceedings. ed. / Mark Wallace. Berlin Germany : Springer, 2004. p. 347-361 (Lecture Notes in Computer Science; Vol. 3258).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Set domain propagation using ROBDDs

AU - Lagoon, Vitaly

AU - Stuckey, Peter J.

N1 - Conference code: 10th

PY - 2004/12/1

Y1 - 2004/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=31144465124&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-30201-8_27

DO - 10.1007/978-3-540-30201-8_27

M3 - Conference Paper

AN - SCOPUS:31144465124

SN - 3540232419

T3 - Lecture Notes in Computer Science

SP - 347

EP - 361

BT - Principles and Practice of Constraint Programming – CP 2004

A2 - Wallace, Mark

PB - Springer

CY - Berlin Germany

T2 - International Conference on Principles and Practice of Constraint Programming 2004

Y2 - 27 September 2004 through 1 October 2004

ER -