Fast set bounds propagation using BDDs

Graeme Gange; Vitaly Lagoon; Peter J. Stuckey

doi:10.3233/978-1-58603-891-5-505

Fast set bounds propagation using BDDs

Graeme Gange, Vitaly Lagoon, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	Frontiers in Artificial Intelligence and Applications
Publisher	IOS Press
Pages	505-509
Number of pages	5
ISBN (Print)	978158603891
DOIs	https://doi.org/10.3233/978-1-58603-891-5-505
Publication status	Published - 1 Jan 2008
Externally published	Yes
Event	European Conference on Artificial Intelligence 2008 - Patras, Greece Duration: 21 Jul 2008 → 25 Jul 2008 Conference number: 18th

Publication series

Name	Frontiers in Artificial Intelligence and Applications
Volume	178
ISSN (Print)	0922-6389

Conference

Conference	European Conference on Artificial Intelligence 2008
Abbreviated title	ECAI 2008
Country/Territory	Greece
City	Patras
Period	21/07/08 → 25/07/08

Access to Document

10.3233/978-1-58603-891-5-505

Cite this

@inproceedings{1ad19a2d91d446ea8859411d439c01f3,

title = "Fast set bounds propagation using BDDs",

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

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

year = "2008",

month = jan,

day = "1",

doi = "10.3233/978-1-58603-891-5-505",

language = "English",

isbn = "978158603891",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press",

pages = "505--509",

booktitle = "Frontiers in Artificial Intelligence and Applications",

address = "Netherlands",

note = "European Conference on Artificial Intelligence 2008, ECAI 2008 ; Conference date: 21-07-2008 Through 25-07-2008",

}

TY - GEN

T1 - Fast set bounds propagation using BDDs

AU - Gange, Graeme

AU - Lagoon, Vitaly

AU - Stuckey, Peter J.

N1 - Conference code: 18th

PY - 2008/1/1

Y1 - 2008/1/1

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

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

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

U2 - 10.3233/978-1-58603-891-5-505

DO - 10.3233/978-1-58603-891-5-505

M3 - Conference Paper

AN - SCOPUS:77957872318

SN - 978158603891

T3 - Frontiers in Artificial Intelligence and Applications

SP - 505

EP - 509

BT - Frontiers in Artificial Intelligence and Applications

PB - IOS Press

T2 - European Conference on Artificial Intelligence 2008

Y2 - 21 July 2008 through 25 July 2008

ER -

Fast set bounds propagation using BDDs

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this