english TASC - INRIA Rennes - LINA CNRS UMR 6241

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:

  1. la taille des problèmes considérés;
  2. la prise en compte simultanée d'aspects temporels et spatiaux; d'aspects discrets et continus;
  3. le caractère dynamique de certains phénomènes induisant une modification des contraintes et des données au cours du temps;
  4. l'expression difficile de certaines contraintes physiques telles, par exemple, l'équilibrage d'un placement ou la stabilité temporelle;
  5. 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.

Références:

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.

Références:

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.

Références:

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.

Références:

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.

Références:

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.

W3C: XHTML - last update : july 2011, SD
up