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

archive