Concilier Expressivité et Efficacité en Programmation par Contraintes

La programmation par contraintes (PPC) a pour objet de résoudre des problèmes ayant une structure combinatoire, qui impliquent des contraintes de formes diverses. Les outils de PPC sont génériques et composables. Ils peuvent facilement être hybridés avec d’autres technologies. Depuis son apparition dans les années soixante-dix, la PPC a suscité un intérêt croissant dans la communauté scientifique. Une des raisons de son succès est qu’il s’agit d’un paradigme théoriquement déclaratif, comme l’avait souligné le Professeur Eugène Freuder : “Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming : The user states the problem, the computer solves it”. Ce pouvoir expressif permet de modéliser un grand nombre d’applications proches les unes des autres sans avoir à implémenter plusieurs fois leurs composants algorithmiques les plus critiques. La PPC est largement employée pour résoudre des problèmes industriels, au détriment parfois, paradoxalement, de sa déclarativité. Il peut en effet s’avérer nécessaire, voire indispensable, de concevoir la modélisation du problème en exploitant fortement des propriétés qui lui sont propres. Cet état de faits comporte le risque d’éliminer à tort certaines idées scientifiques importantes mais trop novatrices pour pouvoir être employées à court terme dans un cadre industriel. Le compromis entre généricité et efficacité se situe donc au cœur de la recherche scientifique en programmation par contraintes. L’objet de cette habilitation est de synthétiser un ensemble de tentatives de réponses à cette problématique, ainsi que les perspectives qui s’en dégagent. Je présente notamment une sélection de contributions portant sur les problèmes d’optimisation : traitement des problèmes sur contraints, de l’incertitude, ainsi que des outils conceptuels permettant une caractérisation des solutions plus fine qu’une notion d’optimalité fonctionnelle classique. Je mets en relief les motivations pratiques et théoriques de ces contributions, leur fil conducteur, ainsi que certaines questions qui demeurent ouvertes. En outre, j’évoque mes travaux sur l’aide à la modélisation de problèmes en programmation par contraintes, par apprentissage, et la génération de conditions de filtrage à partir de représentations génériques des contraintes globales