Conception d'algorithmes de filtrage exploitant le modèle Word-RAM

 

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