La programmation par contraintes
Origine
La programmation par contraintes émerge dans les
années 1980 et se développe au carrefour
des domaines de l'Intelligence Artificielle et de la Recherche
Opérationnelle; de l'informatique et des
mathématiques. Intrinsèquement
multi-disciplinaire, elle ne cesse depuis de s'enrichir de
connaissances issues de connaissances issues de domaines
variés: de la logique, des mathématiques
discrètes et de l'informatique théorique
(théorie des graphes, combinatoire, algorithmique,
complexité), de l'analyse et de l'optimisation
fonctionnelle, du génie logiciel et des systèmes
informatiques. La programmation par contraintes fut
identifiée en 1996 par l'ACM comme une direction
stratégique de recherche en informatique. La JSR
331, standardisation de la programmation par contraintes, a obtenu en
2010 le prix du most
innovative JSR.
Application
L'objet de ce paradigme est la résolution
des problèmes de décision au moyen de
techniques rationnelles, logiques et calculatoires. Avant tout, la
programmation par contraintes est fondée sur la distinction
claire entre la description des contraintes intervenant dans un
problème, d'une part, et les algorithmes et heuristiques
utilisés pour la résolution, d'autre part. C'est
sa capacité à prendre effectivement en compte, de
manière flexible, des contraintes
hétérogènes qui a soulevé
dans les années 1990 un intérêt
commercial pour ce paradigme.
Parmi ses domaines de prédilection, on trouve les
domaines classiques de l'aide à la décision tels
que l'ordonnancement, la planification, le placement, la logistique ou
la finance, ainsi que des domaines moins courants tels que la
conception de circuits électroniques (simulation,
vérification et test), le séquencement d'ADN et
la phylogénie en biologie, la configuration de produits
manufacturiers ou de sites web, l'analyse et la vérification
de code informatique.
Au-delà de la résolution
Les premiers systèmes de programmation par
contraintes imposèrent des restrictions fortes sur la nature
des contraintes que l'on pouvait a priori exprimer
ainsi que sur les techniques de résolution,
génériques, que l'on pouvait utiliser. La
confrontation au monde industriel amena l'introduction de nouvelles
contraintes plus proches des problématiques
rencontrées. Elle conduisit à l'emploi de
techniques de résolution plus efficaces mais aussi de plus
en plus liées aux problèmes
spécifiques considérés. Ce passage du
général au particulier a accompagné le
rattachement progressif de la programmation par contraintes
à la recherche opérationnelle.
À l'heure actuelle, la programmation par
contraintes est souvent comprise comme une simple
ré-appropriation et juxtaposition de techniques issues
d'autres disciplines. Ce constat légitime mais simpliste ne
doit pas faire oublier, d'une part, la complexité
et le profit de cette démarche d'intégration
et, d'autre part, l'objectif original - nouvel et fondateur - de la
programmation par contraintes: couvrir à la fois
les aspects déclaratif et procédural de la
résolution de problèmes, pour aboutir
à des systèmes de résolution
accessibles à tout utilisateur, voire des
systèmes embarqués de résolution
autonomes.
Verrous
Ainsi, un premier verrou auquel fait actuellement face la
programmation par contraintes est la conception de plate-formes de
résolution mettant en oeuvre, de
manière transparente à l'utilisateur,
des techniques efficaces de résolution.
Idéalement, l'utilisateur doit pouvoir décrire
son problème dans un langage de modélisation de
haut niveau sans se préoccuper de la manière de
résoudre son problème. Une telle plate-forme doit
également être indépendante d'un
langage de programmation ou d'un moteur de résolution (solveur)
particulier. Enfin, l'utilisateur doit avoir la possibilité
d'interpréter les solutions retournées dans son
contexte applicatif. Le solveur doit par exemple pouvoir prendre en
compte des problèmes sur-contraints où il est
nécessaire de relâcher en partie les contraintes
spécifiées, et cela de la manière la
plus réaliste possible.
Un second verrou réside dans la
rapidité de résolution et le passage à
l'échelle. Il s'agit de puiser dans les grandes
classes de techniques disponibles à l'heure actuelle
(réseaux de contraintes, algorithmes de graphes,
programmation mathématique, metaheuristiques) et dans les
méthodes ad-hoc développées dont
l'efficacité est avérée, pour les
intégrer dans le cadre de la programmation par contraintes.
Cette intégration engendre de nouvelles
problématiques telles que la conception d'algorithmes
incrémentaux, la décomposition automatique des
problèmes ou la reformulation automatique.
Finalement, un troisième verrou concerne
l'utilisation de la programmation par contraintes dans le cadre de systèmes
industriels complexes. Le caractère complexe a des
causes multiples telles que:
- la taille des problèmes
considérés;
- la prise en compte simultanée d'aspects
temporels et spatiaux; d'aspects discrets et continus;
- le caractère dynamique de certains
phénomènes induisant une modification des
contraintes et des données au cours du temps;
- l'expression difficile de certaines contraintes physiques
telles, par exemple, l'équilibrage d'un placement ou la
stabilité temporelle;
- la décomposition nécessaire des gros
problèmes qui peut fortement dégrader des
performances de résolution.
Axes de recherche de l'équipe
Voir également: bilan,
projet et évaluation AERES 2010.
Objectifs
Les travaux de recherche fondamentale de l'équipe
TASC sont guidés par l'objectif de lever ces verrous:
classifier et enrichir les modèles, automatiser la
reformulation et la résolution, dissocier les connaissances
déclaratives et procédurales,
développer des outils d'aide à la
modélisation et produire des solveurs passant à
l'échelle. Les aspects déclaratifs
de ces recherches sont intégrés dans une base de
connaissance: le catalogue de contraintes. Les aspects
procéduraux sont quand à eux
capitalisés au sein du système de
résolution de contraintes, CHOCO. Enfin, l'équipe
s'emploie, dans le cadre de ses activités de valorisation,
d'enseignement et de recherche partenariale, à l'application
de la programmation par contraintes à la
résolution de problématiques variées.
L'enjeu est, d'une part d'accroître la visibilité
des contraintes dans les autres disciplines de l'informatique, et
d'autre part de contribuer à une plus large diffusion de la
programmation par contraintes dans le monde industriel.
Thèmes fondamentaux
Classification des contraintes globales,
reformulation et filtrage systématique:
La classification systématique des contraintes
globales et de leurs relaxations apporte une vue synthétique
du domaine. Elle établit le lien entre les
propriétés des concepts de bases
utilisés pour décrire les contraintes et les
propriétés des contraintes elles-mêmes.
En collaboration avec SICS, l'équipe a conçu et
maintient un catalogue
de contraintes globales, qui décrit la
sémantique de plus de 300 contraintes,
accompagnée d'une reformulation en termes de
propriétés de graphe ou d'automates. Ces
modèles génériques nous ont permis de
concevoir différents traitements systématiques
des contraintes, et notamment des algorithmes de filtrage
basés sur un ensemble de concepts réduits. Les
questions de la reformulation automatique et de l'apprentissage de
contraintes sont également considérées.
Voir aussi la bibliographie de l'équipe sur ce thème
et les sites web du catalogue de
contraintes globales et du seeker.
Filtrage et consistances:
En parallèle, nous travaillons à la
conception d'algorithmes de maintien de consistance locale et globale,
pour des classes de problèmes donnés. Il s'agit,
souvent à partir de résultats existants (issus de
la théorie des graphes en particulier), d'identifier les
conditions nécessaires de
réalisabilité d'une problématique,
pour ensuite concevoir l'algorithme de filtrage vérifiant et
forçant, de manière incrémentale
durant la recherche, la satisfaction de ces conditions.
Dans un souci d'efficacité, l'effort est mis ici sur la
rapidité des algorithmes avec garantie sur les niveaux de
filtrage produits. La généricité n'est
pas négligée cependant: d'une part, les
modèles étudiés sont applicables dans
de nombreux contextes (par exemple, tree pour le
partitionnement de graphe en logistique comme en
phylogénie); d'autre part, ces travaux ont
débouché sur l'étude de la
portabilité des contraintes et de leur
indépendance aux solveurs. Cet axe de recherche regroupe
divers travaux tels que les consistances locales fortes, les
contraintes de partitionnement de graphe, les contraintes
géométriques, les contraintes d'optimisation et
contraintes souples. Actuellement, dans le but d'attaquer des
problèmes industriels complexes, nous nous
efforçons, par la conception de meta contraintes
telles geost, de répondre
simultanément aux questions de passage à
l'échelle, de dynamicité des contraintes, de
combinaison des dimensions spatiales et temporelles, d'expression de
règles métiers.
Voir aussi la bibliographie de l'équipe sur ce thème.
Explications, problèmes dynamiques
et sur-contraints:
Le concept d'explications
entre dans différents aspects de la programmation par
contraintes, en fonction, encore une fois, du degré
d'automatisation du système. En contexte interactif, la
trace des explications renseigne l'utilisateur sur la
validité de son modèle et sur le
déroulement de la résolution. Elle s'emploie donc
comme un outil d'analyse et de déboggage. En contexte
dynamique, les explications permettent de gérer le retrait
incrémental de contraintes. Elles s'appliquent
également ainsi à la résolution des
problèmes sur-contraints. Enfin, les explications acquises
pendant la résolution indiquent l'état de
l'espace de recherche durant son parcours. Différentes
stratégies dynamiques d'exploration -- complètes
ou incomplètes -- ont été
conçues sur ce concept.
Voir aussi la bibliographie de l'équipe sur les explications/problèmes
dynamiques et sur les sur-contraints
et l'optimisation.
Décompositions et
méthodes hybrides:
Dans ce thème, nous nous intéressons
aux méthodes hybrides combinant la programmation par
contraintes classique (backtracking sur variables
discrètes) avec d'autres formes de résolution
telles que les recherches locales, d'autres
paradigmes telles que la programmation mathématique,
ou encore d'autres environnements telles que les contraintes
numériques ou les contraintes
booléennes. Une difficulté consiste à
faire coopérer les différents
éléments d'une méthode hybride, pour
tirer bénéfice des avantages respectifs des
approches combinées. De manière plus
fondamentale, l'étude des méthodes hybrides
permet de comparer et de relier les stratégies de
résolution propres aux différentes approches pour
ensuite en concevoir de nouvelles.
Voir aussi la bibliographie de l'équipe sur la programmation
mathématique, les recherches locales
et sur les contraintes
continues.
Ces quatres axes ne sont pas indépendants. Les
travaux de l'équipe portent ainsi fréquement sur
des aspects transversaux tels que les contraintes globales
expliquées, la décomposition de Benders par
explications, les contraintes globales souples et pour les
problèmes dynamiques, les modèles et relaxations
linéaires de contraintes.
Les systèmes de
résolution de contraintes: CHOCO et IBEX/QUIMPER
Nos travaux théoriques sont
systématiquement validés par
l'expérimentation, au moyen notamment de la plate-forme de
résolution de contraintes CHOCO.
L'équipe développe et maintient CHOCO avec le
concours du laboratoire e-lab de Bouygues (Guillaume Rochart), de la
société Amadeus (François Laburthe) et
d'autres chercheurs tels que Hadrien Cambazard. Les
fonctionnalités de CHOCO sont progressivement enrichies par
le fruit de nos travaux: conception de contraintes, analyse et
visualisation d'explications, etc. CHOCO, système libre sous
licence BSD, est chargé en moyenne 600 fois par mois.
L'équipe supporte également le
développement d'IBEX,
une librairie C++ sous licence GPL de méthodes
ensemblistes, combinant propagation de contraintes et
méthodes d'intervalles, pour la résolution de
problèmes s'exprimant au moyen de contraintes
numériques (optimisation globale, résolution
d'équations, inversion de modèles, etc.). Elle
est basée sur la programmation par contracteurs,
formalisme implémenté dans le langage haut-niveau
QUIMPER. IBEX/QUIMPER est lauréat des Étoiles du libre'09
et possède aujourd'hui une trentaine d'utilisateurs
académiques réguliers répartis dans
plusieurs laboratoires universitaires (I3S à Nice, UTC
à Compiègne, ENSIETA à Brest, LIRMM
à Montpellier ou IMS à Bordeaux,...).
Ces développements nous ont conduit à de
nouveaux sujets d'études, propres à la conception
et l'implémentation des systèmes de
résolution de contraintes, formant ainsi le
cinquième axe de recherche fondamentale de
l'équipe.
Voir aussi la bibliographie de l'équipe sur ce thème
et les sites web de IBEX
et de CHOCO.
Applications
Une grande partie de nos travaux est consacrée ou
contribue à la résolution de problèmes
pratiques réels issus de domaines d'application
variés, tels que:
Voir aussi la bibliographie de l'équipe sur les applications.
Implication dans la communauté
scientifique
L'équipe TASC, composée d'une vingtaine
de membres, forme l'un des plus importants groupes de chercheurs en
contraintes au niveau international; c'est surtout l'un des plus
ouverts au regard de la diversité des domaines de
compétences.
Ainsi, l'équipe entretient un rôle actif
au sein de la communauté à travers:
- ses activités d'expertise scientifique
(participation régulière aux comités
de programme des deux grandes conférences du domaine, CP et
CPAIOR);
- ses activités d'animation de la
communauté (l'équipe a organisé
l'édition 2006 de la conférence internationale CP
et l'édition 2008 de la conférence francophone
JFPC; N. Jussien a initié en 2004 et
présidé jusqu'en 2009 l'Association
Française de Programmation par Contraintes (AFPC); N.
Jussien et C. Truchet sont membres du bureau de l'AFPC);
- ses activités de promotion et d'ouverture de la
programmation par contraintes aux domaines de la recherche
opérationnelle (S. Demassey, N. Jussien, N. Beldiceanu), de
l'apprentissage et de l'intelligence artificielle (T. Petit, Ph. David,
R. Debruyne), du multimedia (M. Christe, F. Benhamou), de la musique
(C. Truchet), de la combinatoire (J.-X. Rampon).
Organisation de manifestations scientifiques
- CPAIOR'12,
28 mai-1 juin 2012, Nantes
- 9th International Conference on Integration of AI and OR
techniques in Constraint Programming for combinatorial optimisation
problems
- JFPC'08,
4-6 juin 2008, Nantes
- 4èmes Journées Francophones de
Programmation par Contraintes
- CP'06,
25-29 septembre 2006, Nantes
- 12th International Conference on Principles and Practice of
Constraint Programming
- MLS+CP,
28-29 novembre 2005, Nantes
- Workshop on Combination of Metaheuristic and Local Search
with Constraint Programming techniques
- CPAIOR'02,
25-27 mars 2002, Le Croisic
- 4th International Workshop on Integration of AI and OR
techniques in Constraint Programming for combinatorial optimisation
problems
- JFPLC'98,
juin 1998, Nantes
- 7èmes Journées Francophones de
Programmation en Logique et avec Contraintes
Participation à comités de lecture, de
programme
- conférences internationales en contraintes, IA
et RO
- CP
2002-2009, 2011-2012; CPAIOR
2002-2012; AAAI
2004; IJCAI
2005-2006; ECAI
2004, 2006; FLAIRS 2003-2006
- conférences nationales en contraintes, IA et RO
- JFPC 2005-2011; JFPLC
-2004; JNPC -2004; ROADEF 2006-2008,
2012
- autres conférences, workshops et 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
- revues
- 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 de groupes de recherche
- AFPC
- Association Française de Programmation par
Contraintes
- Contraintes et
RO
- groupe de travail du GdR RO, affilié
à la Roadef et à l'AFPC
- Contraintes,
musique et interaction
- groupe de travail affilié à l'AFIM et
à l'AFPC
Responsabilités éditoriales
Formation (cycle gradué)
L'équipe TASC est l'équipe
d'enseignement et de recherche support de la
spécialité de formation d'ingénieur Génie
Informatique pour l'Aide à la Décision (GIPAD)
de l'École des Mines de Nantes.
Les enseignants-chercheurs de l'équipe assurent les
cours Constraint Programming (M2), Advanced Integer Programming (M2) et
Advanced Topics in Optimization (M2) du master ORO de
l'Université de Nantes.
