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

12 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 2013 - Uppsala, Sweden
Duration: 16 Sept 201320 Sept 2013
Conference number: 19th
http://cp2013.a4cp.org/

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 2013
Abbreviated titleCP 2013
Country/TerritorySweden
CityUppsala
Period16/09/1320/09/13
Internet address

Cite this