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

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Konferenceartikel › Forskning › 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.

Originalsprog	Engelsk
Bogserie	Lecture Notes in Computer Science
Sider (fra-til)	318-322
ISSN	0302-9743
DOI	https://doi.org/10.1007/978-3-540-68155-7_30
Status	Udgivet - 2008
Begivenhed	CPAIOR 2008:The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - Paris, Frankrig Varighed: 20 maj 2008 → 23 maj 2008

Konference

Konference	CPAIOR 2008:The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Land/Område	Frankrig
By	Paris
Periode	20/05/2008 → 23/05/2008

Emneord

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

Adgang til dokumentet

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

Citationsformater

@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 -