Explaining propagators for edge-valued decision diagrams

Graeme Gange, Peter J. Stuckey, Pascal Van Hentenryck

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

9 Citations (Scopus)

Abstract

Propagators that combine reasoning about satisfiability and reasoning about the cost of a solution, such as weighted all-different, or global cardinality with costs, can be much more effective than reasoning separately about satisfiability and cost. The cost-mdd constraint is a generic propagator for reasoning about reachability in a multi-decision diagram with costs attached to edges (a generalization of cost-regular). Previous work has demonstrated that adding nogood learning for mdd propagators substantially increases the size and complexity of problems that can be handled by state-of-the-art solvers. In this paper we show how to add explanation to the cost-mdd propagator. We demonstrate on scheduling benchmarks the advantages of a learning cost-mdd global propagator, over both decompositions of cost-mdd and mdd with a separate objective constraint using learning.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 19th International Conference, CP 2013, Proceedings
PublisherSpringer
Pages340-355
Number of pages16
ISBN (Print)9783642406263
DOIs
Publication statusPublished - 22 Oct 2013
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming, CP 2013 - Uppsala, Sweden
Duration: 16 Sep 201320 Sep 2013
Conference number: 19th

Publication series

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming, CP 2013
CountrySweden
CityUppsala
Period16/09/1320/09/13

Cite this

Gange, G., Stuckey, P. J., & Van Hentenryck, P. (2013). Explaining propagators for edge-valued decision diagrams. In Principles and Practice of Constraint Programming - 19th International Conference, CP 2013, Proceedings (pp. 340-355). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8124 LNCS). Springer. https://doi.org/10.1007/978-3-642-40627-0_28