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

- [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

archive