Constraint Programming, Artificial Intelligence and Operational research

Authors | Title | Conference |
---|---|---|

Guillaume Perez, Jean-Charles Régin | MDDs: Sampling and Probability Constraints |
CP 2017 |

Guillaume Perez, Jean-Charles Régin | MDDs are Efficient Modeling Tools: An Application to some Statistical Constraintss |
CPAIOR 2017 |

Guillaume Perez, Jean-Charles Régin | Soft and Cost MDD Propagators |
AAAI 2017 |

Pierre Roy, Guillaume Perez, Jean-Charles Régin, Alexandre Papadopoulos, François Pachet, Marco Marchini | Enforcing Structure on Temporal Sequences: The Allen Constraint |
CP 2016 |

Jordan Demeulenaere, Renaud Hartert, Christophe Lecoutre, Guillaume Perez, Laurent Perron, Jean-Charles Régin, Pierre Schaus | Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets |
CP 2016 |

Guillaume Perez, Jean-Charles Régin | Constructions and In-place Operations for MDDs Based Constraints |
CPAIOR 2016 |

Guillaume Perez, Jean Charles Régin | Efficient Operations On MDDs For Building Constraint Programming Models |
IJCAI 2015 |

Guillaume Perez, Jean Charles Régin | Improving GAC-4 for Table and MDD based constraints |
CP 2014 |

Guillaume Perez, Michel Barlaud, Lionel Fillatre, Jean Charles Régin | A Filtered Bucket-Clustering Method for Projection onto the simplex and the l_1 ball |
GRETSI 2017 |

Guillaume Perez, Jean Charles Régin | Amélioration des opérations sur MDD pour la création de modèle |
JFPC 2016 |

Guillaume Perez, Jean Charles Régin | Relations entre MDDs et Tuples et Modifications dynamique de contraintes MDDs |
JFPC 2015 |

Simon Urli, Guillaume Perez, Heytem Zitoun, Mireille Blay-Fornarino, Philippe Collet, Philippe Renevier |
Vers des interfaces graphiques flexibles de configurations |
JLDP 2012 |

This little part describes some of my works about Multivalued Decision Diagrams (MDDs). My researches about MDDs has been done with my PhD advisor, Jean-Charles Régin.

**MDD Propagator :**we proposed MDD4R ( CP14), the first linear filtering algorithm for MDDs and the faster in practice. This algorithm is the only one capable of dealing with huge MDDs, MDDs having hundreds of millions of nodes.**Soft and Cost version :**We worked on the valued and soft versions of MDDs. We proposed several algorithms for propagating such constraints (AAAI17)**Allen Constraint :**While an MDD can represented several existing constraints without too much work. We have proposed MDD based model for representing more complexe constraint. The first one is the MaxOrder constraint, preventing plagiarism in sequence generation. The second one is the Allen constraint.-
**Statistical Constraints**We have focus on normal law based-constraints in constraint programming. We have proposed algorithms for the existing constraints, proposed a new statistical constraint and its propagator (CPAIOR17)

**Combination :**We worked on operations between MDDs. Generally, MDD operators are mapped from the BDDs ones. They are designed for the function compositions. I have proposed algorithms based on prefix instead of function. These algorithms of combination and reduction have been published at (IJCAI15).**Incrementality :**We proposed an incremental version of the combination and reduction algorithms (CPAIOR16). And we gave some insides about the modification of the compressed set of tuple which is an MDD.**Construction :**We have given several transformations from compressed data structures to MDDs without uncompressing them. A linear algorithm for building an MDD from a table of tuples and some other method or automata etc... (CPAIOR16) (IJCAI15).

**Plagiarism :**Thanks to the combination and reduction proposed, we have solved several text and music generation problems. For example, a problem of generating sequences from a corpus avoiding plagiarism (IJCAI15).**Musical synchronisation :**Thanks to the proposed Allen constraint and a our new model, a problem of music synchronization between several instruments involving several set variables and MDDs have been solved up to 14 musical times. Knowing that existing classical methods failed to solve 3 musical times. Furthermore, the proposed model allows to solve the problem for 6 musical times in less than 2 seconds, allowing the generation in direct.

In this paper, we present the **soft MDD constraint** and provide 3 different methods to handle them: a dedicated
propagator, a transformation into a cost MDD constraint and a transformation into a classical MDD constraint.

**Cost-MDD4R**, a cost MDD propagator is presented. It is based on MDD4R and uses two distinct
resets. The efficiency of this algorithm is showed in the experimental section.

The main problem solved in this paper is the **soft maxOrder problem**. A model is given
and the experimental section show the efficiency of this model.

(Abstract) We introduce Allen, a global constraint relating event indexes with temporal positions. Allen maintains two set-variables: the set of events occurring at a position defined by an Allen relation, and the set of their indexes. These variables enable defining structural and temporal synchronization properties that cannot be stated on indexed variables. We show that a model based on a local scheduling approach does not solve the problem, even for very small instances, highlighting the need for complex filtering. We present a model that uses Multi-valued Decision Diagrams (MDDs) to compile the Allen constraint. We show that this model can be used to state and solve two complex musical tasks: audio track synchronization and musical score generation.

One of the methods presented in this paper is "how to deal with mandatory values inside an MDD". For exemple consider
that the value 'a' becomes mandatory in the following MDD.

As we can see, all the edges of the MDD belong to a valid path. But there exists an invalid path (b,b,b,b). The idea here is that the

In this paper, we describe Compact-Table (CT), a bitwise algorithm to enforce Generalized Arc Consistency (GAC) on table constraints

In this paper we present the **first linear algorithm** for building an MDD from a **table**. We then propose methods for
converting data structures like **GCS** or **tuple sequences** into an MDD.

The main idea for building an MDD from a table is to first build a trie and then build an MDD by using the reduction operation. Since the reduction operation is linear, we have to build the Trie in linear time. The current method need to have an array of the outgoing edges for a random acces While inserting a new tuple. This implies a array whose size is the size of the domaine at each node, this lead to a complexity of O(#nodes * domaineSize). By sorting the table, we directly obtain the Trie. By using ordered list of outgoing edges, we can know is the edge we are looking for exists or not by only checking the last edge of the list.

The second part of this paper focus on how to **remove** an MDD from another **'in-place'**. The 'in-place' specification
implies that we want to modify the MDD of the operation instead of building a resulting MDD. An 'in-place' **addition**
operation is also provided and an **incremental version of the reduction** operator is given. The following animation
show how our 'in-place' deletion algorithm works.

The **poster** for this paper.

This paper first presents several methods for building MDDs, from **automaton**, **Pattern** etc. Then we present a **linear reduction**
algorithm for MDD and an algorithm for the **combination** of MDDs.

The reduction operation consists in merging equivalent nodes. two nodes are equivalent if they have the same sub-MDD
(MDD whose have the node as root).

**pReduce**, the linear reduction algorithm that we provide, start from the bottom of the MDD and put all the nodes
inside a "pack", then split the pack in function of their outgoing edges (label, destination). Since all our
construction methods use and generate ordered list of outgoing edges, then our algorithm will split the nodes in pack having
the same prefix of outgoing edges. The complexity of this algorithm is the sum of common prefixes, which is lower or
equal to the number of edges.

This animation describes how our **reduction** operator works for a layer
(the idea is the same for all the layers). All the nodes are packed inside the blue pack. Then the first edge is checked.
The edge is (0,tt) for 'c' and 'e' and (1,tt) for 'd', so this pack is split into two packs: the blue one {'c','e'} and
the red one {'d'}. Since the red pack contains only one element, we can delete this pack. The algorithm continue
by considering the next edge of 'c' and 'e' which is (1,tt). Here only one pack is created containing {'c','e'}. Finally
no more edges have to be considered for both of them, we can merge them.

The following animation show how our **Apply** operator work for performing the **intersection** of 2 MDDs.

The experimental section focus on solving the MaxOrder problem, which consist in generating sequences based on a coprus (Music or text) avoiding plagiarism. The generated sequences has to follow the transition from the corpus, which implies that each sequence of 2 words in the solution must appears in the original corpus. But No sequences of p words from the original corpus can appears in solution.

**Our model** for solving the MaxOrder problem with maximum plagiarism p=4. The following diagrams
show how to build our model.

This diagram show how from the corpus, we can first extract the Markov automata and then build the 'Markov MDD'
by using our creation method for automata (describe below). This 'Markov MDD' is defined over 4 variables.

Then we extract from the corpus all the sequences of lenght 4 and build the 'Prohibited sequences MDD'. An important
remark is that this 'Prohibited sequences MDD' is included into the 'Markov MDD'. Then we use apply operator that
we propose and delete the 'Prohibited sequences MDD' from the 'Markov MDD'. We obtain 'MDD V' containing all the Markov
transitions but no plagiarism sequences.

Using this 'MDD V', we can either build a first model by applying this MDD constraint over all the 4 consecutives
variables, or we can perform the intersection of all of them. The next paragraph gives the resulting MDD .
An allDifferent constraint was also in our model.

MDD used for the last experiment.
After the intersections. 20 variables, 10785 values, ~1 200 000 nodes, ~190 000 000 edges and 2.2*10^35 tuples

(format: startEdge1, endEdge1, valueEdge1, startEdge2, ...)

In this paper we also present another method to efficiently build an MDD from an automaton. Since the classical
method simply builds the MDD by unrolling the automaton from the root node and by associating each created node with a
state. Then while processing a node, look into the transition table the outgoing transitions for this node (state).

For example we want to build an MDD representing this automata for 3 variables:

The Application of this method will give the following processing:

Here we propose another method. We first build at each layer as many node than states. Then we simple read once the
transition table and for each transition, we put an edge between the states for all the layers. The following animation
show how our method build the same MDD.

One of the reasons of this method is that we need to 'stream' the transition table in one of our problems.

In the experimental part, our reduction is compared to the state of the art method (DFS + hash), and we can see that our method outperfoms the other. The experimental section also show that our creation methods for automaton and pattern is very efficient in practice. Another part of the experiment show that a ternary decomposition of an MDD is outperformed by MDD4R, even using the best current table propagators.

In this paper, we describe GAC-4R, a table constraint propagator, based on the famous GAC-4 algorithm. We also introduce MDD4R, an MDD constraint propagator, also using the idea of GAC-4. MDD4R maintains the whole MDD during the search, and maintains for each value of each variable, the set of valid edges supporting the value.

When a modification occurs in the domain of a variable, MDD4R will perfoms 2 BFS for propagating the modifications. One starting from the modified layer to the top, another one from the modified layer to the bottom.

**Reset Idea: ** The reset idea appears when we have for example 90% of
a data structure that have to be remove, while we could only work with the 10% remaining.
Both of these algorithms use the idea of reset.

The two following images show the edges considered while performing the affectation of the value 1 for the second
variable.

MDD4 (without reset):
MDD4R (with reset):

The first one show 6 red edges, this implies that 6 edges have been removed.
The second one show two green edges and one red edge, this implies that 2 edges have been restored and one edges
has been remove. This result show that MDD4R (with reset) has considered less edges than without reset.
The processing of both of the algorithms is given in the following animations:

MDD4 (without reset):
MDD4R (with reset):

The experiment part show that both MDD4R and GAC-4R are very efficient in practice.

The source code of both MDD4R and GAC-4R are available from the OscaR solver and from the ortools solver.