Annonce de thèse Microsoft Research au GREYC (Caen)

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 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 start in May and continue until a suitable candidate has been found.