frenchTASC - INRIA Rennes - LINA CNRS UMR 6241

Constraint Programming


Constraint programming emerges in the eighties and develops at the intersection of Artificial Intelligence and Operations Research, of Computer Science and Mathematics. Multidisciplinary by nature it keeps on using knowledge from various topics such as discrete mathematics, theoretical computer science (graph theory, combinatorics, algorithmic, complexity), functional analysis and optimization, IT and software engineering. Constraint programming was identified in 1996 by the ACM as a strategic topic for Computer Science. The JSR 331, standardization of constraint programming, won in 2010 the award of the most innovative JSR.


Constraint programming deals with the resolution of decision problems by means of rational, logical and computational techniques. Above all, constraint programming is founded on a clear distinction between, on the one hand the description of the constraints intervening in a problem, and on the other hand the techniques used for the resolution. The ability of constraint programming to handle in a flexible way heterogeneous constraints has raised the commercial interest for this paradigm in the early nighties.

Among his fields of predilection, one finds traditional applications such as computer aided decision making, scheduling, planning, placement, logistics or finance, as well as applications such as electronic circuits design (simulation, checking and test), DNA sequencing and phylogeny in biology, configuration of manufacturing products or web sites, formal verification of code.

Beyond Solving

The first constraint programming systems imposed strong restrictions both on the nature of the constraints that one could express and on the resolution techniques one could use. Confrontation with the industrial world brought the introduction of new constraints closer to the kind of problems met in practice. It led to the use of more effective solving techniques that were more and more related to the specificities of the considered problems. This passage from generic to dedicated techniques has foster the progressive fastening of constraint programming to operational research.

Nowadays constraint programming is often understood as a simple appropriation and juxtaposition of techniques resulting from other disciplines. Even if this is true, one should not forget the complexity and benefit of this integration as well as the primary objective of constraint programming: covering at the same time the declarative and procedural aspects of problem solving, in order to lead to decision support systems accessible to any type of user or embedded within autonomous systems.


Thus, a first challenge encountered by constraint programming is the design of computer systems implementing in a transparent way effective solving techniques. Ideally, the user must be able to describe his problem in a high level modeling language without being concerned with the underlying solving mechanisms used. Such systems must also be independent both from any computer programming language and from any resolution engine. Lastly, the user must have the ability to interpret the returned solutions, in particular within the context of over constrained problems where it is necessary to partly relax some constraints, and that in the most realistic possible way.

A second challenge resides in the speed of resolution especially in the context of large scale data. One has to adapt techniques such as constraint networks, graph algorithms, mathematical programming, meta-heuristics and to integrate them within the framework of constraint programming. This integration generates new questionings such as the design of incremental algorithms, the automatic decomposition or the automatic reformulation of problems.

Finally a third challenge deals with the use of constraint programming in the context of complex industrial problems. Complexity have multiple causes such as:

  1. the size of the considered problems,
  2. the combination of temporal and spatial aspects, of continuous and discrete aspects,
  3. the dynamic character of some phenomena inducing a modification of the constraints and data during time,
  4. the difficulty of expressing some physical constraints, e.g. load balancing and temporal stability,
  5. the necessary decomposition of large problems inducing significant solution performance losses.

Research directions of the TASC team

See also: project and assessment AERES 2010.


Basic research of the TASC team is guided by the challenges raised before: to classify and enrich the models, to automate reformulation and resolution, to dissociate declarative and procedural knowledge, to develop modelling tools and to come up with solving tools that scale well. On the one hand, classification aspects of this research are integrated within a knowledge base about combinatorial problem solving: the global constraint catalog. On the other hand, solving aspects are capitalized within the constraint solving system CHOCO. Lastly, within the framework of its activities of valorization, teaching and of partnership research, the team uses constraint programming for solving various concrete problems. The challenge is, on one side to increase the visibility of the constraints in the others disciplines of computer science, and on the other side to contribute to a broader diffusion of the constraint programming in the industry.

Fundamental research topics

Global constraints classification, reformulation and filtering:

The systematic classification of global constraints and of their relaxation brings a synthetic view of the field. It establishes links between the properties of the concepts used to describe constraints and the properties of the constraints themselves. Together with SICS, the team develops and maintains a catalog of global constraints, which describes the semantics of more than 300 constraints expressed in terms of graph properties and automata. These generic models enabled us to conceive various systematic treatments attached to constraints, and in particular of the generic filtering algorithms. Work on automatic reformulation of models and constraint learning is also done.

Selected references:

See also the team bibliography on this topic and the Global Constraint Catalog and its seeker websites.

Filtering and consistency:

In parallel, we design algorithms that maintain local and global consistencies, for more specific models. Having in mind the trade off between genericity and effectiveness, the effort is put on the efficiency of the algorithms with guarantee on the produced levels of filtering. This effort results in adapting existing techniques of resolution such as graph algorithms. For this purpose we identify necessary conditions of realisability that can be evaluated by efficient incremental algorithms. Genericity is not neglected in these approaches: on the one hand the constraints we focus on are applicable in many contexts (for example, graph partitioning constraints can be used both in logistics and in phylogeny); on the other hand, this work led to study the portability of such constraints and their independence with specific solvers. This research orientation gathers various work such as strong local consistencies, graph partitioning constraints, geometrical constraints, and optimisation and soft constraints. Within the perspective to deal with complex industrial problems, we currently develop meta constraints (e.g., geost) handling all together the issues of large scale problems, dynamic constraints, combination of spatial and temporal dimensions, expression of business rules.

Selected references:

See also the team bibliography on this topic.

Explanation, dynamic and over constrained problems:

The concept of explanations impacts various aspects of constraints programming, depending on the required degree of automation of the system. In the context of interactive systems, the explanation log informs the user about the validity of his model and the status of the resolution. Consequently it can be used like an analysis and debugging tool. In the context of dynamic problems, explanations make it possible to manage the incremental withdrawal of constraints. They can also be used for the resolution of overstrained problems. Lastly, explanations acquired during the resolution reflect the status of the search space explored so far. Various dynamic search strategies -- complete or incomplete -- were based on this concept.

Selected references:

See also the team bibliography on explanations/dynamic and optimization/over-constrained.

Decompositions and hybrid methods:

This topic deals with hybrid methods combining traditional constraint programming (backtracking for discrete variables) with other forms of resolution such as local search, with other paradigms such as mathematical programming, or with other environments such as the numerical or boolean constraints. One challenge consists in making cooperate the various elements of a hybrid method, to draw benefit from the respective advantages of the combined approaches. More fundamentally, the study of hybrid methods makes it possible to compare and connect strategies of resolution specific to each approach for then conceiving new strategies.

Selected references:

See also the team bibliography on mathematical programming, local search, numeric constraints.

These four research topics are in fact not independent. The work of the team thus frequently relates transverse aspects such as explained global constraints, decomposition of Benders and explanations, flexible and dynamic constraints, linear models and relaxations of constraints.

Constraint Solving Systems: CHOCO and IBEX/QUIMPER

Our theoretical work is systematically validated by concrete experimentations. We have in particular for that purpose the CHOCO constraint platform. The team develops and maintains CHOCO with the assistance of the laboratory e-lab of Bouygues (Guillaume Rochart), the company Amadeus (François Laburthe), and others researchers such as Hadrien Cambazard. The functionalities of CHOCO are gradually extended with the outcomes of our works: design of constraints, analyzes and visualization of explanations, etc. The open source CHOCO library is downloaded on average 600 times each month.

The team also supports the development of IBEX, an open-source C++ library for set computation, combining constraint propagation and interval methods, for solving problems with numerical constraints (global optimization, equation solving, model inversion, etc.). It is based on the contractor programming formalism, implemented in the high-level language QUIMPER. IBEX/QUIMPER is regularly used in several academic research labs (I3S/Nice, UTC/Compiègne, ENSIETA/Brest, LIRMM/Montpellier, IMS/Bordeaux,...).

These developments led us to new research topics, concerned with the design and the development of solvers, thus forming the fifth direction of basic research of the team.

Selected references:

See also the team bibliography on this topic and the IBEX and CHOCO websites.


A large part of our work is dedicated or contributes to solve practical problems in various application domains, such as:

See also the team bibliography on applications.

Activities within the scientific community

The TASC team (about 20 members) forms one of the most important groups of researchers in constraints at the international level; It is also one of the most open group with respect to the diversity of its fields of competence.

Thus, the team maintains an active role within the community through:

  • activities of scientific expertise (regularly involved within the program committee of the two biggest conferences of the domain, namely CP and CPAIOR),
  • the organization of scientific events (the team has organized the 2006 edition of the CP international conference and the 2008 edition of the JFPC national conference). N. Jussien has initiated in 2004 and chaired until 2009 the French association for constraint programming (AFPC); N. Jussien and C. Truchet are members of the AFPC board,
  • the promotion of constraint programming to domains like operations research (S. Demassey, N. Jussien, N. Beldiceanu), music (C. Truchet), learning and artificial intelligence (T. Petit, P. David, R. Debruyne), multimedia (M. Christie, F. Benhamou), combinatorics (J.-X. Rampon).

Organisation of conferences

CPAIOR'12, may 28-june 1, 2012, Nantes
9th International Conference on Integration of AI and OR techniques in Constraint Programming for combinatorial optimisation problems
JFPC'08, june 4-6, 2008, Nantes
4èmes Journées Francophones de Programmation par Contraintes
CP'06, september 25-29, 2006, Nantes
12th International Conference on Principles and Practice of Constraint Programming
MLS+CP, november 28-29, 2005, Nantes
Workshop on Combination of Metaheuristic and Local Search with Constraint Programming techniques
CPAIOR'02, march 25-27, 2002, Le Croisic
4th International Workshop on Integration of AI and OR techniques in Constraint Programming for combinatorial optimisation problems
JFPLC'98, june 1998, Nantes
7èmes Journées Francophones de Programmation en Logique et avec Contraintes

Participation to program committee

CP, IA and OR international conferences
CP 2002-2009, 2011-2012; CPAIOR 2002-2012; AAAI 2004; IJCAI 2005-2006; ECAI 2004, 2006; FLAIRS 2003-2006
CP, IA and OR national conferences
JFPC 2005-2011; JFPLC -2004; JNPC -2004; ROADEF 2006-2008, 2012
other conferences, workshops and tracks
Doctoral-CP 2011; MELO 2011, MODELS 2011; ACM-SAC 2005-2013; LION 2007, 2009-2012; RIVF 2007, 2008, 2012; ISMIR 2008; SOFSEM 2007; PADL 2006; MOPGP 2006; CPTools 2006; Beyond FD 2006; RJCIA 2005; CHANGES 2005; ICMC 2005
Constraints, Artificial Intelligence, IJAIT, Mathematical Programming, Discrete Optimization, Journal of Scheduling, Journal of Heuristics, Annals of Operations Research, European Journal of Operational Research, Rairo-RO, Reliable Computing, Theory and Practice of Logic Programming

Animation of research associations

French Association for Constraint Programming
working group of the GdR RO (CNRS), affiliated to Roadef and to AFPC
Constraints, music and interaction
working group affiliated to AFIM and to AFPC

Editorial duties

Teaching (graduate school)

The team fully supports the Computer Science for Decision Support (GIPAD) graduate specialty of the engineer school of École des Mines de Nantes.

Members of the team teach the Constraint Programming (M2), Advanced Integer Programming (M2), and Advanced Topics in Optimization (M2) courses of the ORO master of Nantes university.

W3C: XHTML - last update : july 2011, SD