Skip to content. | Skip to navigation

Emergences

Lettre d'information n° 23

Image emergences pour impression
Personal tools
You are here: Home 2012 Lettre d'information n° 23 Les vertus de la programmation par contraintes
Document Actions

Les vertus de la programmation par contraintes

Équipe de recherche commune d'Inria, de l'École des Mines de Nantes, de l'université de Nantes et du CNRS, Tasc* explore le potentiel de la programmation par contraintes. Au carrefour des mathématiques et de l'informatique, cette discipline aussi appelée PPC permet d'aborder les problèmes combinatoires de grande échelle, comme l'explique le scientifique Nicolas Beldiceanu.

Équipe de recherche commune d'Inria, de l'École des Mines de Nantes, de l'université de Nantes et du CNRS, Tasc* explore le potentiel de la programmation par contraintes. Au carrefour des mathématiques et de l'informatique, cette discipline aussi appelée PPC permet d'aborder les problèmes combinatoires de grande échelle, comme l'explique le scientifique Nicolas Beldiceanu.

Nous récupérons souvent les problèmes que d'autres méthodes ne peuvent guère traiter, résume malicieusement Nicolas Beldiceanu, responsable de l'équipe Tasc. La programmation par contraintes convient pour les problèmes dans lesquels il y a un aspect combinatoire se mêlant à des contraintes opérationnelles complexes : la planification, le placement et l'ordonnancement par exemple.” Né dans les années 1980, ce paradigme établit une distinction claire entre la description des contraintes intervenant dans un problème et les techniques utilisées pour le résoudre. Les applications concernent l'aide à la décision dans de nombreux domaines tels que la logistique ou la gestion de ‘data centres’.

Ainsi, en ce moment, notre équipe participe à la création d'un outil de pré-programmation urbaine.” L'enjeu : la conception de villes durables de A à Z. Développé à travers le projet collaboratif Sustains, “ce logiciel aidera les architectes et les urbanistes à prendre en compte quantité d'aspects comme la croissance démographique, la mixité sociale, les transports, les taux d'emploi, la topographie, les besoins énergétiques...” Autant de contraintes dont l'optimisation tient du casse-tête. “Et clairement, ce n'est pas uniquement le génie logiciel qui peut répondre à des problèmes de ce type combinatoire.

Les ‘smart grids’ 

Les chercheurs de Tasc collaborent aussi avec un industriel du secteur énergie. Un des volets de ce rapprochement porte sur les smart grids. À la fois complexes et dynamiques, ces réseaux de distribution intelligents tissent une relation nouvelle entre producteurs et consommateurs d'énergie. “Ce genre de réseau fait intervenir à la fois des mathématiques discrètes et des mathématiques continues. Et c'est ce qui nous intéresse.  Il faut concilier d'un côté la re-configuration dynamique à grande échelle et de l'autre la garantie d'une production suffisante. Dans l'avenir, je pense que ces aspects discret/continu deviendront un axe de recherche important. Une des complications résulte du fait que le sujet concerne des communautés de recherche très différentes issues du discret (combinatoire, graphe) et du continu (analyse numérique).  L'équipe de recherche nantaise réunit donc des spécialistes des deux mondes.

 Les travaux de Tasc suscitent aussi l'intérêt du centre de R&D de Google à Paris. “Ils travaillent sur les contraintes. Ils développent un outil en interne, mais pourraient intégrer éventuellement certains de nos algorithmes de filtrage. Google a financé une partie de nos recherches sur les explications dans les contraintes. Celles-ci permettent de pointer telle ou telle raison pour laquelle un ensemble de contraintes n'a pas de solution.

Dans le souci d'élaborer des outils génériques plutôt que des logiciels à usage unique, les chercheurs se concentrent sur l'enrichissement de bibliothèques de contraintes open source à l'instar de Choco. Initiée par l'entreprise Amadeus et le laboratoire e-lab du groupe Bouygues, cette librairie Java est désormais intégrée en situation réelle dans nombre d'applications. L'équipe concourt également au développent d'Ibex, une bibliothèque C++ élaborée principalement par Gilles Chabert et initiée par lui quand il était doctorant au centre de recherche Inria de Sophia Antipolis.

 Catalogue de librairies

Au fil des ans, dans le monde, bien d'autres bibliothèques ont vu le jour : Ilog Solver, JaCoP, Gecode, OR-tools, SICStus Prolog… “Mais hélas elles ne sont qu'un éternel recommencement d'une implémentation de contraintes dans un langage d'accueil (Java, C++, Prolog...). Voilà l'une des raisons qui nous a incité à entreprendre un travail de catalogage des contraintes.” Mais la principale motivation se trouve ailleurs. “Encodées par des développeurs dans un langage donné, ces librairies semblent avoir été comme figées dans le marbre. L'idée du catalogue, c'est donc aussi de décrire tous les aspects des contraintes, de manière explicite, à l'aide de méta-données. Une fois les contraintes ainsi décrites, on va pouvoir utiliser une même contrainte pour différents usages. Y compris des utilisations qui n'étaient pas vraiment initialement prévues.

Dans une nouvelle étape, les chercheurs se dirigent maintenant vers l'apprentissage de modèles de contraintes indépendamment de la technologie (contrainte, SAT, programmation linéaire). Mais “nous n'en sommes pas au stade où l'on peut résoudre complétement automatiquement des problèmes. En optimisation, il existe différentes technologies avec leur communautés respectives. Cependant, aucune n'a émergé comme un standard à la façon d'un SQL pour les bases de données. On peut espérer qu'il y en aura grâce à cette approche basée sur la capitalisation des connaissances sous forme de méta données. Mais ce n'est pas évident.

* Theory, Algorithms, and Systems for Constraints. TASC est une équipe commune Inria Rennes - Bretagne Atlantique, Ecole des Mines de Nantes, Université de Nantes, CNRS.