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 language | English |
---|---|
Title of host publication | Principles and Practice of Constraint Programming - 19th International Conference, CP 2013, Proceedings |
Publisher | Springer |
Pages | 340-355 |
Number of pages | 16 |
ISBN (Print) | 9783642406263 |
DOIs | |
Publication status | Published - 22 Oct 2013 |
Externally published | Yes |
Event | International Conference on Principles and Practice of Constraint Programming 2013 - Uppsala, Sweden Duration: 16 Sept 2013 → 20 Sept 2013 Conference number: 19th http://cp2013.a4cp.org/ |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 8124 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Conference on Principles and Practice of Constraint Programming 2013 |
---|---|
Abbreviated title | CP 2013 |
Country/Territory | Sweden |
City | Uppsala |
Period | 16/09/13 → 20/09/13 |
Internet address |