The 20th International Conference on
Principles and Practice of
Constraint Programming
Lyon, France
8-12 September 2014

First Workshop on Bridging the Gap Between Theory and Practice in Constraint Solvers

Aims and scope

For several years now, CP and SAT solvers have made tremendous advances that allow them to solve very large instances.
If the methods used to achieve this efficiency in practice are well-known, there does not exist to date any analytical explanation to justify the operational efficiency that seems totally at odds with the theoretical complexity of the problems addressed.
On the other hand, many studies have been developed for a long time on the detection of tractable classes in different areas or formalisms such as CSP, SAT, in planning, etc.
But these tractable classes are hardly ever used in practice and thus are generally not explicitly implemented in the solvers.
However, these two bodies of work seem to have been developed in parallel rather than in synergy, creating a real gap between these two aspects of constraint programming.

The purpose of this workshop is to better understand the reasons for the effectiveness of solvers, and also promote exchanges between researchers from both sides of the CP communities with the aim to reduce the gap between these two types of work.
The expected contributions cover a wide spectrum ranging from theoretical works on tractable classes, to implementations of solvers.
They also concern the work on performance analysis of solvers.
And ideally, work on the study of the properties explaining the behavior of efficient solvers.

We solicit original papers, but papers already published in journals or presented in conferences, particularly if they associate theory and practice are welcome.
This call for papers also includes position papers aimed at creating constructive and fruitful discussion
between researchers working in theory and practice.

The workshop will be held as a full-day or half-day workshop. Please note that workshop-participants need to be registered for the workshop.

This workshop would like to bring together researchers interested in :

- implementation of solvers
- optimization of solvers
- analysis of solvers
- study and analysis of benchmarks
- experimentations
- analysis of practical efficiency
- competition of solvers
- complexity analysis
- tractability
- tractable classes
- complexity theory


Room Blaise Pascal (335)

09:00-09:05 Opening

09:05-10:00 Invited Talk: Solving Function Problems with SAT Oracles [Joao Marques-Silva]

10:00-10:30 Coffee break

10:30-12:30 Technical Session 1:

10:30-11:10 Searching for a maximum common induced subgraph by decomposing the compatibility graph
[M. Minot and S. N. Ndiaye]

11:10-11:50 Hidden Tractable Classes
[A. EL Mouelhi, P. Jégou and C. Terrioux]

11:50-12:30 Detecting and Exploiting Subproblem Tractability
[C. Bessiere, C. Carbonnel, E. Hebrard, G. Katsirelos, T. Walsh]

12:30-14:00 Lunch break

14:00-16:00 Technical Session 2 & Open discussion

14:00-14:40 Analysis of SatPlan-2006 on the instances of the International Planning Competitions IPC4 and IPC5
[S. Grandcolas and C. Pain-Barre]

14:40-15:20 Computing q-Horn Strong Backdoor Sets: a preliminary experimentation
[R. Ostrowski and L. Paris]

15:20-16:00 Open discussion

16:00 End of the Workshop and Coffee break


This workshop is sponsored by the Project TUPLES ( :

Tractability for Understanding and Pushing forward the Limits of Efficient Solvers

of the French National Agency for Research.

Important Dates

Submission date: July 10, 2014
Notification of acceptance: July 25, 2014
Camera ready version: August 15, 2014
Workshop day: September 8, 2014


Submissions must be formatted in the Lecture Notes in Computer Science (LNCS) style and must be at most 15 pages, excluding references. Submissions of short papers (no constraint for their lenght), including position papers, are welcome.

Papers must be submitted in PDF format by email to

All submissions will be reviewed and those that are well-written and make a worthwhile contribution to the topic of the workshop will be accepted for publication in the workshop proceedings. The proceedings will be available electronically at CP 2014. At least one author of each accepted paper must attend the workshop. Please note that every workshop participant needs to be registered for the workshop.

Invited speaker

Joao Marques-Silva


- Philippe Jégou (main contact), LSIS - UMR CNRS 7296, Universite d'Aix-Marseille, France
- Martin Cooper, IRIT, Université de Toulouse III, France
- Lakhdar Saïs, CRIL - CNRS, UMR 8188, Université Lille Nord de France, Artois, France

- Bruno Zanuttini, GREYC - UMR CNRS 6072, Universite de Caen Basse-Normandie, France

Program Committee

- David Cohen (Royal Holloway, University of London, UK)
- Martin Cooper (IRIT-CNRS, Université de Toulouse III, France)
- Stéphane Grandcolas (LSIS-CNRS, Universite d'Aix-Marseille, France)
- Emmanuel Hébrard (LAAS-CNRS, France)
- Peter Jeavons (University of Oxford, UK)
- Philippe Jégou (LSIS-CNRS, Universite d'Aix-Marseille, France)
- Daniel Le Berre (CRIL-CNRS, Université Lille Nord de France, Artois, France)
- Fred Maris (IRIT-CNRS, Université de Toulouse III, France)
- Pierre Marquis (CRIL-CNRS, Université Lille Nord de France, Artois, France)
- Bertand Mazure (CRIL-CNRS, Université Lille Nord de France, Artois, France)
- Cyril Pain-Barre (LSIS-CNRS, Universite d'Aix-Marseille, France)
- Lionel Paris (LSIS-CNRS, Universite d'Aix-Marseille, France)
- Pierre Régnier (IRIT-CNRS, Université de Toulouse III, France)
- Lakhdar Saïs (CRIL-CNRS, Université Lille Nord de France, Artois, France)
- Cyril Terrioux (LSIS-CNRS, Universite d'Aix-Marseille, France)
- Bruno Zanuttini (GREYC-CNRS, Universite de Caen Basse-Normandie, France)