Research

Constraint Programming, Artificial Intelligence and Operational research

Publications

My works - Google scholar - DBLP - CV - GitHub

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

Compressed data structures and optimization

Guillaume Perez - Advisor: Jean-Charles Régin

I3S laboratory - Sophia Antipolis, France

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.

MDDs in Constraint Programming

  • 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)

Algorithmic and Data Structures

  • 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).

Applications

  • 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.

Poster 2016

Description of some publications

Soft and Cost MDD Propagators

Guillaume Perez, Jean Charles Régin

AAAI 2017

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.

Enforcing Structure on Temporal Sequences: The Allen Constraint

Pierre Roy, Guillaume Perez, Jean-Charles Régin, Alexandre Papadopoulos, François Pachet, Marco Marchini

CP 2016

(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 full valid MDD (the MDD containing only valid paths) is not a sub-graph of the original MDD. But the full invalid MDD is a sub-graph of the original MDD. To extract this sub-graph we first delete the edges labeled by the mandatory value (here 'a') and propagate these deletions. we obtain an MDD containing all the invalid paths. Now we can use the In-Place deletion operator for removing this MDD from the original. The result is the last frame of the animation.

Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets

Jordan Demeulenaere, Renaud Hartert, Christophe Lecoutre, Guillaume Perez, Laurent Perron, Jean-Charles Régin, Pierre Schaus

CP 2016

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

Constructions and In-place Operations for MDDs Based Constraints

Guillaume Perez, Jean Charles Régin

CPAIOR 2016

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.

Efficient Operations On MDDs For Building Constraint Programming Models

Guillaume Perez, Jean Charles Régin

IJCAI 2015

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.

Improving GAC-4 for Table and MDD based constraints

Guillaume Perez, Jean Charles Régin

CP 2014

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.