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

10 Citations (Scopus)


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
Number of pages16
ISBN (Print)9783642406263
Publication statusPublished - 22 Oct 2013
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 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


ConferenceInternational Conference on Principles and Practice of Constraint Programming 2013
Abbreviated titleCP 2013
Internet address

Cite this