Claude-Guy Quimper
Université Laval
Domaine : technologies de l'information et des communications
Programme établissement de nouveaux chercheurs universitaires
Concours 2011-2012
Les solveurs de contraintes peuvent résoudre des problèmes combinatoires complexes comme l'ordonnancement des atterrissages d'avions dans les aéroports, la confection d'horaires de travail dans les entreprises, la planification d'un tournoi sportif, la création de l'horaire des salles dans une université, etc. Ces solveurs utilisent des algorithmes qui filtrent l'espace de recherche en éliminant les solutions candidates qui ne satisfont pas tous les critères. Puisque les propagateurs sont exécutés des milliers voire des millions de fois dans la résolution d'un problème, toute amélioration, même minime, se traduit par des gains important en performance.
Les récentes percées en algorithmique permettent de concevoir des algorithmes qui utilisent le plein potentiel des nouveaux processeurs. Ceux-ci peuvent, en une seule instruction, traiter chacun des 64 bits se trouvant dans un même mot. Ces nouvelles structures de données qui sont conçues et analysées en utilisant le modèle dit « Word-RAM » permettent d'accroître l'efficacité des algorithmes.
Nous proposons de concevoir de nouveaux algorithmes de filtrage pour les solveurs de contraintes basés sur le modèle Word-RAM. Ces propagateurs utiliseront des structures de données rapides qui amélioreront la performance des solveurs de contraintes. Les solveurs pourront alors résoudre les problèmes plus rapidement ou obtenir de meilleures solutions pour un temps de calcul donné.