Dynamic analysis of bounds versus domain propagation

Christian Schulte; Peter J. Stuckey

doi:10.1007/978-3-540-89982-2_32

Dynamic analysis of bounds versus domain propagation

Christian Schulte, Peter J. Stuckey

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

1 Citation (Scopus)

Abstract

Constraint propagation solvers interleave propagation (removing impossible values from variable domains) with search. Previously, Schulte and Stuckey introduced the use of static analysis to determine where in a constraint program domain propagators can be replaced by more efficient bounds propagators and still ensure that the same search space is traversed. This paper introduces a dynamic yet considerably simpler approach to uncover the same information. The information is obtained by a linear time traversal of an analysis graph that straightforwardly reflects the properties of propagators implementing constraints. Experiments confirm that the simple dynamic method is efficient and that it can be used interleaved with search, taking advantage of the simplification of the constraint graph that arises from search.

Original language	English
Title of host publication	Logic Programming - 24th International Conference, ICLP 2008, Proceedings
Pages	332-346
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-540-89982-2_32
Publication status	Published - 1 Dec 2008
Externally published	Yes
Event	International Conference on Logic Programming 2008 - Udine, Italy Duration: 9 Dec 2008 → 13 Dec 2008 Conference number: 24th https://link.springer.com/book/10.1007/978-3-540-89982-2 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5366 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Logic Programming 2008
Abbreviated title	ICLP 2008
Country/Territory	Italy
City	Udine
Period	9/12/08 → 13/12/08
Internet address	https://link.springer.com/book/10.1007/978-3-540-89982-2 (Proceedings)

Access to Document

10.1007/978-3-540-89982-2_32

Cite this

Schulte, C., & Stuckey, P. J. (2008). Dynamic analysis of bounds versus domain propagation. In Logic Programming - 24th International Conference, ICLP 2008, Proceedings (pp. 332-346). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5366 LNCS). https://doi.org/10.1007/978-3-540-89982-2_32

@inproceedings{580c0cb492474ab38d78f7e7c28f8c35,

title = "Dynamic analysis of bounds versus domain propagation",

abstract = "Constraint propagation solvers interleave propagation (removing impossible values from variable domains) with search. Previously, Schulte and Stuckey introduced the use of static analysis to determine where in a constraint program domain propagators can be replaced by more efficient bounds propagators and still ensure that the same search space is traversed. This paper introduces a dynamic yet considerably simpler approach to uncover the same information. The information is obtained by a linear time traversal of an analysis graph that straightforwardly reflects the properties of propagators implementing constraints. Experiments confirm that the simple dynamic method is efficient and that it can be used interleaved with search, taking advantage of the simplification of the constraint graph that arises from search.",

author = "Christian Schulte and Stuckey, {Peter J.}",

year = "2008",

month = dec,

day = "1",

doi = "10.1007/978-3-540-89982-2_32",

language = "English",

isbn = "3540899812",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "332--346",

booktitle = "Logic Programming - 24th International Conference, ICLP 2008, Proceedings",

note = "International Conference on Logic Programming 2008, ICLP 2008 ; Conference date: 09-12-2008 Through 13-12-2008",

url = "https://link.springer.com/book/10.1007/978-3-540-89982-2",

}

Schulte, C & Stuckey, PJ 2008, Dynamic analysis of bounds versus domain propagation. in Logic Programming - 24th International Conference, ICLP 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5366 LNCS, pp. 332-346, International Conference on Logic Programming 2008, Udine, Italy, 9/12/08. https://doi.org/10.1007/978-3-540-89982-2_32

Dynamic analysis of bounds versus domain propagation. / Schulte, Christian; Stuckey, Peter J.

Logic Programming - 24th International Conference, ICLP 2008, Proceedings. 2008. p. 332-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5366 LNCS).

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

TY - GEN

T1 - Dynamic analysis of bounds versus domain propagation

AU - Schulte, Christian

AU - Stuckey, Peter J.

N1 - Conference code: 24th

PY - 2008/12/1

Y1 - 2008/12/1

N2 - Constraint propagation solvers interleave propagation (removing impossible values from variable domains) with search. Previously, Schulte and Stuckey introduced the use of static analysis to determine where in a constraint program domain propagators can be replaced by more efficient bounds propagators and still ensure that the same search space is traversed. This paper introduces a dynamic yet considerably simpler approach to uncover the same information. The information is obtained by a linear time traversal of an analysis graph that straightforwardly reflects the properties of propagators implementing constraints. Experiments confirm that the simple dynamic method is efficient and that it can be used interleaved with search, taking advantage of the simplification of the constraint graph that arises from search.

AB - Constraint propagation solvers interleave propagation (removing impossible values from variable domains) with search. Previously, Schulte and Stuckey introduced the use of static analysis to determine where in a constraint program domain propagators can be replaced by more efficient bounds propagators and still ensure that the same search space is traversed. This paper introduces a dynamic yet considerably simpler approach to uncover the same information. The information is obtained by a linear time traversal of an analysis graph that straightforwardly reflects the properties of propagators implementing constraints. Experiments confirm that the simple dynamic method is efficient and that it can be used interleaved with search, taking advantage of the simplification of the constraint graph that arises from search.

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

U2 - 10.1007/978-3-540-89982-2_32

DO - 10.1007/978-3-540-89982-2_32

M3 - Conference Paper

AN - SCOPUS:58549119821

SN - 3540899812

SN - 9783540899815

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 332

EP - 346

BT - Logic Programming - 24th International Conference, ICLP 2008, Proceedings

T2 - International Conference on Logic Programming 2008

Y2 - 9 December 2008 through 13 December 2008

ER -

Dynamic analysis of bounds versus domain propagation

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this