IRILL - Research and Innovation on Free Software -
Charlotte TRUCHET (STMS UM 9912, Sorbonne Université, Ircam, CNRS) :
« Introduction à la programmation par contraintes, et aux problèmes de programmation qu’elle pose »
Résumé :
La programmation par contraintes s’attache à résoudre des problèmes fortement combinatoires, exprimés à l’aide de relations logiques (les contraintes), portant sur des variables dans des domaines fixés, souvent finis. Chaque contrainte est dotée d’un algorithme de propagation, qui élague autant que possible les domaines des variables sans perdre de solutions. Les solveurs appliquent ces propagateurs tant que c’est possible, puis effectuent des choix (affectation d’une valeur à une variable, réduction d’un domaine) et itèrent le processus. On sait aujourd’hui résoudre des familles de contraintes assez larges (cardinalité, graphes, mots, géométrie…). Mais les mécanismes internes des solveurs posent des problèmes d’implémentation pas toujours simples. Dans cet exposé, nous présenterons les notions principales du domaine (contraintes, domaines, consistance, propagation, heuristiques) puis nous explorerons la question de l’efficacité pratique d’un de ces algorithmes (filtrage de la contrainte alldifferent). Enfin, nous examinerons les difficultés que l’on rencontre pour implémenter ce résultat théorique, en pratique, dans un solveur.