Propagating separable equalities in an MDD store

Tarik Hadzic; John N. Hooker; Peter Tiedemann

doi:10.1007/978-3-540-68155-7_30

Propagating separable equalities in an MDD store

Tarik Hadzic, John N. Hooker, Peter Tiedemann

Research output: Journal Article or Conference Article in Journal › Conference article › Research › peer-review

Abstract

We present a propagator that achieves MDD consistency for a separable equality over an MDD (multivalued decision diagram) store in pseudo-polynomial time. We integrate the propagator into a constraint solver based on an MDD store introduced in [1]. Our experiments show that the new propagator provides substantial computational advantage over propagation of two inequality constraints, and that the advantage increases when the maximum width of the MDD store increases.

Original language	English
Book series	Lecture Notes in Computer Science
Pages (from-to)	318-322
ISSN	0302-9743
DOIs	https://doi.org/10.1007/978-3-540-68155-7_30
Publication status	Published - 2008
Event	CPAIOR 2008:The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - Paris, France Duration: 20 May 2008 → 23 May 2008

Conference

Conference	CPAIOR 2008:The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Country/Territory	France
City	Paris
Period	20/05/2008 → 23/05/2008

Keywords

MDD consistency
Separable equality
Pseudo-polynomial time
Constraint solver
Computational advantage

Access to Document

10.1007/978-3-540-68155-7_30

Cite this

@inproceedings{304487a08bb211dd8006000ea68e967b,

title = "Propagating separable equalities in an MDD store",

abstract = "We present a propagator that achieves MDD consistency for a separable equality over an MDD (multivalued decision diagram) store in pseudo-polynomial time. We integrate the propagator into a constraint solver based on an MDD store introduced in [1]. Our experiments show that the new propagator provides substantial computational advantage over propagation of two inequality constraints, and that the advantage increases when the maximum width of the MDD store increases. ",

keywords = "MDD consistency, Separable equality, Pseudo-polynomial time, Constraint solver, Computational advantage, MDD consistency, Separable equality, Pseudo-polynomial time, Constraint solver, Computational advantage",

author = "Tarik Hadzic and Hooker, {John N.} and Peter Tiedemann",

note = "Serie: Lecture Notes in Computer ScienceIntegration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Springer, 5015, 0302-9743, 1611-3349 Volumne: 5015; CPAIOR 2008:The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems ; Conference date: 20-05-2008 Through 23-05-2008",

year = "2008",

doi = "10.1007/978-3-540-68155-7_30",

language = "English",

pages = "318--322",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

TY - GEN

T1 - Propagating separable equalities in an MDD store

AU - Hadzic, Tarik

AU - Hooker, John N.

AU - Tiedemann, Peter

N1 - Serie: Lecture Notes in Computer ScienceIntegration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Springer, 5015, 0302-9743, 1611-3349 Volumne: 5015

PY - 2008

Y1 - 2008

N2 - We present a propagator that achieves MDD consistency for a separable equality over an MDD (multivalued decision diagram) store in pseudo-polynomial time. We integrate the propagator into a constraint solver based on an MDD store introduced in [1]. Our experiments show that the new propagator provides substantial computational advantage over propagation of two inequality constraints, and that the advantage increases when the maximum width of the MDD store increases.

AB - We present a propagator that achieves MDD consistency for a separable equality over an MDD (multivalued decision diagram) store in pseudo-polynomial time. We integrate the propagator into a constraint solver based on an MDD store introduced in [1]. Our experiments show that the new propagator provides substantial computational advantage over propagation of two inequality constraints, and that the advantage increases when the maximum width of the MDD store increases.

KW - MDD consistency

KW - Separable equality

KW - Pseudo-polynomial time

KW - Constraint solver

KW - Computational advantage

KW - MDD consistency

KW - Separable equality

KW - Pseudo-polynomial time

KW - Constraint solver

KW - Computational advantage

U2 - 10.1007/978-3-540-68155-7_30

DO - 10.1007/978-3-540-68155-7_30

M3 - Conference article

SN - 0302-9743

SP - 318

EP - 322

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - CPAIOR 2008:The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

Y2 - 20 May 2008 through 23 May 2008

ER -