Programmation par Contraintes

Christine Solnon - 2003


"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."
(La programmation par contraintes représente une des avancées que l'informatique ait jamais réalisée qui se rapproche le plus du Saint Graal de la programmation : l'utilisateur définit le problème, l'ordinateur le résout.)

Eugene C. Freuder

Avertissement : Ce cours est destiné aux étudiants de la e-miage, une formation informatique "à distance". Il est découpé en 7 sessions de cours, chaque session étant prévue pour durer approximativement 1 heure.

Présentation générale du cours

La notion de contrainte est très (trop !) naturellement présente dans notre vie quotidienne, qu'il s'agisse d'affecter des stages à des étudiants en respectant leurs souhaits, de ranger des pièces de formes diverses dans une boîte rigide, de planifier le trafic aérien pour que tous les avions puissent décoller et atterrir sans se percuter, ou encore d'établir un menu à la fois équilibré et appétissant. La notion de "Problème de Satisfaction de Contraintes" (ou CSP en abrégé, pour Constraint Satisfaction Problem) désigne l'ensemble de ces problèmes, définis par des contraintes, et consistant à chercher une solution les respectant.
La première session de ce cours introduira les notions de contraintes, de problèmes de satisfaction de contraintes (CSPs) et de solution d'un CSP. Lors de la deuxième session, vous vous entraînerez, à travers plusieurs exercices, à modéliser un problème sous la forme d'un CSP.
La résolution de CSP est généralement combinatoire dans le sens où il faut envisager un très grand nombre de combinaisons avant d'en trouver une qui satisfasse toutes les contraintes (... parfois même, le nombre de combinaisons est infini...). Bien souvent, la puissance de calcul des ordinateurs ne suffit pas pour examiner toutes les combinaisons possibles en un temps acceptable, et il est nécessaire d'introduire des "raisonnements" et des "heuristiques" permettant de réduire la combinatoire et de guider la recherche vers les bonnes combinaisons. En ce sens, la résolution pratique de CSPs fait appel à des techniques issues traditionnellement de "l'intelligence artificielle".
Lors de la troisième session de ce cours, on présentera l'algorithme de base utilisé pour résoudre les CSPs sur les domaines finis, algorithme basé sur l'énumération des combinaisons. On étudiera un certain nombre d'heuristiques et techniques de filtrage permettant d'améliorer cet algorithme. Lors de la quatrième session, on programmera ces différents algorithmes en Prolog, et on les utilisera pour résoudre différents CSPs modélisés lors des deux premières sessions de cours.
Ces algorithmes permettant de résoudre des CSPs sont appelés des "solveurs" de contraintes. Certains de ces solveurs ont été intégrés dans des langages de programmation, définissant ainsi un nouveau "paradigme" de programmation appelé "programmation par contraintes" : pour résoudre un CSP avec un langage de programmation par contraintes, il suffit de spécifier les contraintes, leur résolution étant prise en charge automatiquement (sans avoir besoin de le programmer) par les solveurs de contraintes intégrés au langage.
La cinquième session de ce cours sera dédiée à la présentation d'un langage de programmation par contraintes, à savoir Gnu-Prolog. Enfin, les deux dernières sessions seront des sessions de travaux pratiques, où vous utiliserez les solveurs de contraintes intégrés à Gnu-Prolog pour résoudre les différents exercices vus lors des sessions précédentes.

Pour en savoir plus sur les problèmes de satisfaction de contraintes et la programmation par contraintes :


Sommaire du cours :