Open Postdoc position, LINA, Nantes, France (8 months)

TITLE: Probabilistic analysis of global constraints behavior

We are looking for a candidate holding a PhD in computer science, with an
expertise in Constraint Programming and programmation in Java. Ideally, the
candidate should have an interest in mathematics, preferably in probability
theory. The candidate will work in the TASC team in Nantes, and be involved in
the ANR Boole project, and work in collaboration with the project partners, and
in particular D. Gardy (PRiSM UMR 8144, FR-78035 Versailles, France).

Contacts: Charlotte.Truchet@univ-nantes.fr, Xavier.Lorca@mines-nantes.fr
Keywords: Constraint Programming, probabilistic models, constraint propagation,
Choco solver.

JOB DESCRIPTION
In Constraint Programming (CP) [1], the propagation mechanism is one of the key
tools for solving hard combinatorial problems. It is based on specific
algorithms, called propagators, that are called an important number of times
during the resolution process. In practice, these algorithms may do nothing:
their output is equal to their input. This yields the question of a good
balance between the algorithms time complexity and their effective performance,
as identified by [2]. In previous works [3], we proposed to quantify this
phenomenon in the particular case of the alldifferent constraint (bound
consistency propagator). We rely on a probabilistic model for the entry of this
propagator to compute the probability that it actually modifies its input, and
give an asymptotical estimation that can be computed in constant time.

These works rely on some hypothesis on the distribution of the variables
domains during the solving process. These hypothesis need to be tested in
real-life situations, on a wide benchmark. From the results analysis, a
freezing strategy will then be defined: depending on the expected gain of the
propagator, it can be either called or frozen in the propagation loop. This
will be done in a new version of Choco [4], a CP solver in Java developed by
the TASC team, where the propagation loop can be finely tuned thanks to a
dedicated language.

POSTDOC MISSION
The postdoc candidate will be in charge of designing a methodology to observe
the validity of the probabilistic model, and quantify the expected gain when
freezing the propagators. From this, he/she will develop a freezing strategy in
Choco and test it on real-life applications. He/she can possibly participate in
further research on this subject, extending the probabilistic model to other
cardinality constraints.

WORKING ENVIRONMENT
This postdoc is funded by the BOOLE project, supported by the French research
agency (ANR) and led by Versailles University (http://boole.prism.uvsq.fr/).
The project includes academic researchers from 12 Universities or research
centers, with a main focus on the study of boolean formulas with tools at the
interface between mathematics and computer science.

The candidate will work in the TASC team in Nantes
(http://www.emn.fr/z-info/ppc/), which gathers around 20 researchers both from
Nantes University and the Ecole des Mines de Nantes. In practice, he/she will
be at the Ecole des Mines de Nantes (4 rue Alfred Kastler, BP 20722, F-44307
Nantes Cedex 03).

The monthly net salary is 2000 euros and the contract is for 8 months.

References.
[1] F. Rossi, P. van Beek and T. Walsh Ed., Handbook of Constraint Programming,
Elsevier, 2006
[2] I. Katriel, Expected-Case Analysis for Delayed Filtering, in Proc.
CPAIOR2006, pp119-125, LNCS
[3] J. du Boisberranger, D. Gardy, X. Lorca and C. Truchet. When is it
worthwhile to propagate a constraint? A probabilistic analysis of ALLDIFFERENT.
Accepted to Analco 2013, Meeting on Analytic Algorithmics and Combinatorics, to
appear.
[4] Choco Team. choco: an open source java constraint programming library.
Research report 10-02-INFO, Ecole des Mines de Nantes, 2010.