Constraint Programming
Origin
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.
Application
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.
Challenges
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:
- the size of the considered problems,
- the combination of temporal and spatial aspects, of
continuous and discrete aspects,
- the dynamic character of some phenomena inducing a
modification of the constraints and data during time,
- the difficulty of expressing some physical constraints,
e.g. load balancing and temporal stability,
- the necessary decomposition of large problems inducing
significant solution performance losses.
Research directions of the TASC team
See also: project
and assessment AERES 2010.
Objectives
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.
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.
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.
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.
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.
See also the team bibliography on this topic and
the IBEX
and CHOCO websites.
Applications
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
- journals
- 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
- AFPC
- French Association for Constraint Programming
- CP+OR
- 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.
