Constraint Programming, Artificial Intelligence and Operational research


My PhD Thesis - My works - Google scholar - DBLP - CV - GitHub

Authors Title Conference
Guillaume Perez, Jean-Charles Régin Parallel Algorithms for Operations on Multi-valued Decision Diagrams AAAI 2018
Junwen Bai, Sebastian Ament, Guillaume Perez, John Gregoire, Carla Gomes An Efficient Relaxed Projection Method for Constrained Non-negative Matrix Factorization with Application to the Phase-Mapping Problem in Materials Science CPAIOR 2018
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

PhD thesis: Decision Diagrams: Constraints and Algorithms

Advisor: Jean-Charles Régin

I3S laboratory - Sophia Antipolis, France

My PhD Thesis - Defended 29th September 2017

Poster 2016
The three parts of my thesis are described below.

Part 1: MDDs Manipulations

  • Creation: MDDs allow to build many problems, and often without enumerating all their solutions. This property is useful when modeling sub-problems containing huge amount of solutions, many values and variables. Moreover, MDDs can be created from many data sources, for example, they can be built from Boolean formulas or dynamic programming. In this thesis, we focus on improving some of the existing conversion, like the ones from tables or automaton. Then we propose new creation methods from several existing compressed data structures like the global cut seed and the tuple sequences.
  • Reduction: MDDs have a strong compression power. They allow for example in this thesis, to model a complex sub-problem having more than 10^{90} solutions and defined over more than one hundred variables, using an MDD having slightly more than 600,000 arcs. MDDs are often used because of their strong compression power, which mostly comes from the reduction of the MDD. The reduction of an MDD is an operation which merges equivalent nodes, thus allowing the MDD to enforce compression. Throughout the years, several algorithms have been proposed. In this thesis, we propose a linear reduction algorithm, which is especially well suited for large set of different values. We also propose a incremental version of this algorithm, well suited for consecutive operations.
  • Combination: One of the most fundamental aspect of MDDs is their ability to be easily combined. They offer an efficient way to combine constraints that are difficult otherwise. This allows to solve many problems by building MDDs for sub-problems and combining them. These are the reasons why this thesis is going to focus on how to efficiently use MDDs for solving problems. Consider a problem containing p constraints, building an MDD for each constraint and intersecting them lead to an MDD containing all the solutions of the problem. Even if such a method is not always possible, combining MDDs often drastically improves the resolution time, by solving sub-part of the problems. Combining MDDs is a well studied topic, and as for the reduction, several algorithms have already been proposed. In this thesis, we propose to study the existing algorithms, to enlight some of their weaknesses and to propose new versions strengthening them.
  • Advanced operations: Thanks to the simple definition of our new algorithms for the creation, reduction, and combination, we are able to improve and extend them by first designing parallel algorithms. These parallel algorithms have a linear gain factor over the number of workers and allow to process huge MDDs in few seconds. We also propose algorithm for the relaxed MDDs, one of the hot topic of MDD and combinatorial optimization. Finally, we also consider non deterministic MDDs. Such MDDs can allow us to gain another exponential in size.

Part 2: MDDs in Constraint Programming

  • MDD Propagator: The use of MDDs inside of constraint programming solver is done using MDD propagators. We proposed MDD4R, a linear filtering algorithm for MDDs and often the faster in practice. A particularity of this algorithm is its ability of handling "huge" MDDs: MDDs having hundreds of millions of nodes. This is mainly due to its reset mode, allowing to rebuild from scratch some data structures, when it is less coslty than a fully incremental approach.
  • Cost MDD propagator: In combinatorial optimization, an objective function is optimized. A cost MDD constraint, is a constraint allowing to constrain the cost of the solution inside of an MDD. We proposed several algorithms for propagating such constraints. First by defining an efficient ad-hoc algorithm. Then by using a simple transformation of cost MDD constraint onto simple MDD constraint, trading space against efficiency.
  • Soft MDD propagator: Often no exact solution exists in real world problem. This implies that, in combinatorial otpimization, no assignement of the variables satisfying all the constraints exists. We call such problem over constrained problems. In such a configuration, the users often allow to violate some constraints, but with respect to a violation measurement. We call these violable constraints "soft constraints". In my these, we propose the forst algorithm allowing to handle soft MDD constraints. We also propose two polynomial transormations allowing to handle soft MDD constraints using either cost MDD propagator or even simple MDD propagators.
  • 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: In many application, the variables are known to follow a given statistical distribution. Also, using statistical distribution like a normal law over the workload of agents can allow to have well balanced solution. Thus we have first improve algorithm allowing to handle spread like constraints. Then we have propose algorithms and propagators allowing to handle any probability mass function or Markov Chain as a constraint by constraining the probability of solutions.

Part 3: MDDs Applications

Thanks to the new combination and reduction algorithms proposed, we have been able to solve several text and music generation problems.

  • Avoiding Plagiarism: While generating music or text, an important aspect is to generate new content. If we let the machine generate sequences based on a corpus without being careful, the machine can simply reproduce the content of the corpus. Thus several works have focus on how to prevent a content generation algorithms to generate plagiarism sequences. In this thesis, we propose to handle this problem using MDDs. We show that this method is well suited for such problems and that MDDs even allow to combine other constraints up with the plagiarism constraint.
  • Musical synchronisation: Thanks to the proposed Allen constraint and a new model proposed in this thesis, We are able to solve a problem of music synchronization between several instruments. This problem involves several set variables and MDDs. While most classical method fail to solve the problem for more than 3 musical times, we have solved up to 14 musical times in less than 2 minutes and 6 musical times in less than 2 seconds.

Reinforcement Learning

Context Parallel: In constraint programming, the parallel version of a search is an important question. The Embarrassingly parallel search (EPS - CP13 - Régin et al.) is a method consisting at generating a set of at least P sub-problems by doing a kind of Breadth-first search on the search space. Then a set of W workers randomly pick sub-problems and solve them independently. When no more sub-problems are left and all the worker are done, then the problem is solved.

Context Search Strategy: In constraint programming, the search strategy guides the resolution. Many search strategies exist. For a given problem, the choice of a search strategy against another one can drastically change the run time.

In the paper "Parallel Strategies Selection" (CP16 - Palmieri, Régin, Schaus), the problem is to find, for each sub-problem, the best search strategy. The paper propose two methods, one based on a statistical test, and another one using a reinforcement learning Algorithm. We describe here the second method.