Programmation par contraintes : théorie, applications et enseignement

 

Description

La programmation par contraintes, proposée par Jean Louis Laurière en 1976, est un paradigme de modélisation et de résolution de problèmes combinatoires. Un tel modèle se décompose en variables, en leur domaine discret représenté en extension et en des relations les reliant, et devant être toujours satisfaites. L’algorithme permettant d’activer un tel modèle, et d’exhiber éventuellement une valeur de chaque domaine pour chaque variable, est basé sur la notion de retour-arrière (chronologique, saut arrière, dirigé par les conflits) et sur la notion de consistance de nœud, d’arc ou de chemin. Ce paradigme connait un grand succès depuis 35 ans et est passé depuis plusieurs décennies dans l’industrie, au moyen de nombreux outils informatiques (par ex., IBM, COSYTEC, ECLIPSE, Prolog).

Dans cet exposé, nous présentons la théorie de la programmation par contraintes (principalement, sa formalisation algorithmique), plusieurs applications (par ex., aéroportuaires), ainsi qu’un retour sur son enseignement en M1.