Charlotte Truchet (LINA, Nantes)

Historiquement liée à l’Intelligence Artificielle, la Programmation par Contraintes (CP) est aujourd’hui très tournée vers la résolution pratique de problèmes fortement combinatoires, avec de nombreux algorithmes subtils et dédiés (contraintes globales). Le cadre générique de la CP permet d’exprimer des problèmes variés d’une façon uniforme, et de les résoudre dans un même solveur, qui s’occupe notamment de combiner les contraintes globales. On obtient ainsi des solveurs très efficaces sous certaines hypothèses, l’une d’entre elles étant que le solveur soit bien paramètre (heuristiques de choix de variables, de choix de valeurs, gestion de la boucle de propagation). En résumé, les solveurs de contraintes offrent des outils très puissants, réservés aux experts de la discipline.

Nous pensons que l’un des obstacles à des paramétrages automatisés des solveurs est la maigre connaissance que l’on a de leur comportement : bien souvent, les contraintes globales sont analysées en pire des cas, ce qui n’apporte aucune information utile sur leur efficacité réelle. Dans cet exposé, nous identifierons un certain nombre de problèmes qui gagneraient à être analysés en moyenne, fût-ce grossièrement ou approximativement.