Paper Info
Title
Efficient Operations Between MDDs and Constraints
Abstract
Many problems can be solved by performing operations between Multi-valued Decision Diagrams (MDDs), for example in music or text generation. Often these operations involve an MDD that represents the result of past operations and a new constraint. This approach is efficient, but it is very difficult to implement with some constraints such as alldifferent or cardinality constraints because it is often impossible to represent them by an MDD because of their size (e.g. a permutation constraint involving n variables requires $$2^n$$ nodes). In this paper, we propose to build on-the-fly MDDs of structured constraints as the operator needs them. For example, we show how to realise the intersection between an MDD and an alldifferent constraint by never constructing more than the parts of the alldifferent constraint that will be used to perform the intersection. In addition we show that we can anticipate some reductions (i.e. merge of MDD nodes) that normally occur after the end of the operation. We prove that our method can be exponentially better than building the whole MDD beforehand and we present a direct application of our method to construct constraint MDDs without having to construct some intermediate states that will be removed by the reduction process. At last, we give some experimental results confirming the gains of our approach in practice.
Year
DOI
Venue
2022
10.1007/978-3-031-08011-1_13
Integration of Constraint Programming, Artificial Intelligence, and Operations Research
DocType
ISSN
Citations 
Conference
0302-9743
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Jung Victor100.34
Jean-charles Régin2131296.59