PhD position in Constraint Satisfaction (LSIS-Marseille-France)

Title: Graph and hypergraph decomposition methods for solving constraint
satisfaction problems using restart techniques.

Laboratory: Aix-Marseille University, Laboratoire des Sciences de
l’Information et des Systèmes (LSIS) – UMR CNRS 7296 – Marseilles – France

Advisors: Philippe Jégou, Cyril Terrioux

Short abstract:

The topic of this research project is at the border of mathematics and
computer science. Although located in the domain of the foundations of
constraint programming, this subject is based on the fundamental problem
of graph (and hypergraph) decomposition [1,2]. It is well known that
constraint satisfaction problems (CSPs), also called constraint
networks, can be represented by graphs or hypergraphs. While solving
CSPs is an NP-hard task, when the structure of the constraint networks
has some nice topological properties, they can be solved efficiently
using decomposition [3]. In summary, the subject proposed here focuses
on the improvement of techniques for solving constraint satisfaction
problems using decomposition and by exploiting the concept of
“restarts”. When solving a combinatorial problem, in the case where an
area of the search space is extremely difficult to solve, the most
efficient solvers exploit the notion of restart which is to continue the
search for a solution, starting from another area of the search space.
This kind of techniques is one of the key points of the most efficient
solvers [4,5,6] and has been exploited for the first time recently in
[7] with graph decomposition. The integration of such a technique
induces practical problems, but also more fundamental questions related
to the concept of decomposition of graphs (or hypergraphs). Indeed, its
implementation would require to define the notion of dynamic
decomposition, for which it does not exist to date theoretical tools.
So, the work will be focused on the development of theoretical tools for
graph decompositions adapted to the management of this kind of
dynamicity, and to their practical validation.

[1] N. Robertson, P.D. Seymour, ‘Graph minors II: Algorithmic aspects of
tree-width’, Algorithms 7, p. 309– 322, 1986.
[2] G. Gottlob, N. Leone, F. Scarcello, ‘A comparison of structural CSP
decomposition methods’, Artificial Intelligence,124-2, p.243-282, 2000.
[3] P. Jégou, C. Terrioux, ‘Hybrid backtracking bounded by
tree-decomposition of constraint networks’, Artificial Intelligence,
146, p. 43–75, 2003.
[4] N. Eén, N. Sörensson, ‘An Extensible SAT-solver’, SAT, p. 502–518.

1. [5] C. Lecoutre, ‘Constraint Networks Techniques and Algorithms’.
   ISTE/Wiley, 2009.
   [6] A. Atserias, J. K. Fichte, M. Thurley, ‘Clause-Learning Algorithms
   with Many Restarts and Bounded-Width Resolution’, Journal of Artificial
   Intelligence Research (JAIR) 40, p. 353–373. 2011.
   [7] P. Jégou, C. Terrioux, ‘Combining Restarts, Nogoods and
   Decompositions for Solving CSPs’, in Proceedings of ECAI’14, 2014, to
   appear.

These works will be realised at the LSIS laboratory (UMR CNRS 7296) in
Marseilles, France (http://www.lsis.org). The applicant will be member
of the INCA team of LSIS. This research team has been ranked A+ (the
best possible ranking) by the French National Agency for Evaluation of
Research (AERES).

Keyword: CSP, SAT, algorithmics, graph decomposition, complexity,
tractable classes, solvers.

Location: University of Aix-Marseille, Faculty of Sciences, LSIS, Marseilles

Funding: the Ph.D. fellowship is funded for 3 years and is monthly
funded about approximatively 1600 €.

Candidate Profile: Applicants should have (or in the process of getting)
a M.Sc. in Computer Science, Computer Engineering or a closely-related
discipline (as Discrete Mathematics). Strong algorithmic and
mathematical skills are required. C++ or C development skills are
desirable. The knowledge of French is not required.

Start date: the position starts preferably in September / October 2014.

Application and contacts: Candidates must send their application before
June 20th 2014 midnight:
- CV (at most 3 pages)
- Results and ranking for the M.Sc. (join a copy of marks)
- a cover letter,
- reference letters.
Applications must be sent by email with pdf files to
philippe.jegou@univ-amu.fr and cyril.terrioux@univ-amu.fr