Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 2 Février 2016

La programmation par contraintes a besoin d’analyse en moyenne

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr