# Annonce de thèse Microsoft Research / GREYC (Caen) en Programmation par Contraintes

Une allocation de thèse Microsoft Research est disponible au GREYC (Caen) pour la rentrée prochaine.

Sujet : Multi-Stage Constraint Programming.

Constraint solving is a set of techniques for solving combinatorial and
optimization problems. In this thesis, we propose to study an extension called
Quantified Constraint Programming (QCSP), which is an extension of constraint
programming in which some of the variables are universally quantified. For
example, the formula *exists x* *in {1, 2, 3}, forall* *y* *in {3, 4}, exists*
*z* *in* *{4, 5, 6} . x < y and* *x+y = z and* *z ≠ 3x* defines a quantified
constraint program. The most intuitive way of entering the new scenario is by
thinking of it as a game between two players. One player is associated to the
existential quantifier, the other is related to the universal quantifier. The
goal of the existential player is to satisfy each constraint, hence to satisfy
the whole CSP. The goal of the universal player is to violate at least one
constraint, thus overcoming the opponent’s effort. The two players play
against each other in turn, for a finite and fixed number of rounds. The
solution of such a problem is a tree called *strategy* and assigns a value for
each existential variable in function of its preceding universal ones. Finding
a strategy is a complex problem since QCSP have been proven to be Pspace-
complete. The purpose of this thesis is to leverage QCSP techniques in order
to build an environment to solve efficiently multi-stage optimization
problems.

The candidate should have an outstanding degree in computer science, a solid background in artificial intelligence and algorithms. A first experience in research and/or in constraint programming is highly recommended. In addition, strong coding skills in C++ are required. Prior knowledge of french is not mandatory.

Applicants should submit in a zip file their CV, copy of their university degrees, a list of publications if any, a cover letter and the name of three referees by email to Arnaud Lallouet, arnaud.lallouet@unicaen.fr, http://users.info.unicaen.fr/~alalloue/. Selected candidates are expected to come for an interview in the lab or by visio-conference. Interviews will continue until a suitable candidate has been found.

archive