Habilitation defense
Charlotte Truchet
Towards A Less Constrained Constraint Programming
Using Abstract Interpretation and Average-case Analysis to Define Expressive, Easy to Tune Solvers
The defense will be on Thursday, November 30th 2017, at 10am, at the LS2N in Nantes, bâtiment 11, salle 3.
The traditional "pot" is at 16:30 in the same room.
On December 1st (the day after), there will be a workshop with members of the jury, of the Coverif ANR project and of the TASC team at LS2N. It is open to everybody.
Jury
- Mme Nadia Creignou, Professeure, Aix-Marseille Université, reviewer
- M. Christian Schulte, Professor, KTH Royal Institute of Technology, Sweden, reviewer
- M. Pascal Van Hentenryck, Professor, University of Michigan, USA, reviewer
- M. Gérard Assayag, Directeur de Recherches, IRCAM
- M. Frédéric Benhamou, Professeur, Université de Nantes
- M. Eric Goubault, Professeur, Ecole Polytechnique
- M. Thomas Jensen, Directeur de Recherches, INRIA
- Mme Brigitte Vallée, Directrice de Recherches, CNRS
Documents
- The dissertation is available here.
- A vitae is available here.
How to find the room
The defense will be at the Faculty of Sciences of the University of Nantes. Instructions to find the campus can be found here. The building is number 11 on the map of the campus.
The room 3 is on the ground floor, right of the entrance.
Abstract
Constraint Programming (CP) provides efficient methods to model and solve combinatorial problems. Constraint solvers are fast, yet not easy to use for non-computer scientists. In this thesis, we first present a CP application to urban planning, and describe the constraints holding on non-expert users of the CP technology. Our contributions aim at relaxing (part of) these constraints. They are organized on two axes. Firstly, we present a series of average-case analyses of some inner mechanisms of the CP solving process: random restart for local search, speed-ups of parallel multiwalk local search and incremental consistency of the global alldifferent constraint. These theoretical analyses provide useful insights to understand, and tune, these mechanisms. Secondly, we introduce a generic solving process on more expressive domains than the usual CP domains, based on the abstract domains as defined in Abstract Interpretation. We present new such abstract domains: relational ones (octagons and polyhedra) and combined ones (boxes-polyhedra and integer-real reduced products). Ultimately, our goal is to have each single constraint solved in the abstract domain best fit for it. These collaborations with two other fields, Applied Mathematics and Semantic, enhance both CP expressivity and ease-of-use, a necessary condition to widen its application spectrum.