Efficient Operations On MDDs for Building Constraint Programming Models

For instance, phrase generation problem involves domains having more than d 10, 000 values. Thus, We propose improved algorithms for defining the we cannot use an algorithm whose time or space complexity most common operations on Multi-Valued Decision is mainly based on Ω(nd), where n is the number of nodes Diagrams (MDDs): creation, reduction, complement, of the MDDs. Therefore, we need to improve the algorithms intersection, union, difference, symmetric performing the main operations on MDDs: creation, reduction difference, complement of union and complement and combinations. of intersection. Then, we show that with these algorithms The new creation algorithm we propose, exploits the origin and thanks to the recent development of an of the definition of the MDD. If the MDD represents an automaton efficient algorithm establishing arc consistency for (like with a regular constraint) or a repeated pattern MDD based constraints (MDD4R), we can simply (like with dynamic programming), then its creation may be solve some problems by modeling them as a set of sped-up.