2016 | OriginalPaper | Chapter
MDD Propagation for sequence Constraints
Authors : David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John Hooker
Published in: Decision Diagrams for Optimization
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this chapter we present a detailed study of MDD propagation for the sequence constraint. This constraint can be applied to combinatorial problems such as employee rostering and car manufacturing. It will serve to illustrate the main challenges when studying MDD propagation for a new constraint type: Tractability, design of the propagation algorithm, and practical efficiency. In particular, we show in this chapter that establishing MDD consistency for sequence is NP-hard, but fixed-parameter tractable. Furthermore, we present an MDD propagation algorithm that may not establish MDD consistency, but is highly effective in practice when compared to conventional domain propagation.