Séminaire GIGL : Nouvel algorithme de filtrage pour le raisonnement énergétique de la contrainte Cumulative
Consulté 312 fois
Titre : Nouvel algorithme de filtrage pour le raisonnement énergétique de la contrainte Cumulative
Conférencière : Claude-Guy Quimper
Résumé : En programmation par contraintes, la contrainte Cumulative permet de modéliser des problèmes d'ordonnancement où n tâches s'exécutent sans interruption. Des tâches peuvent s'exécuter simultanément pourvu que le taux d'utilisation total de la ressource ne dépasse pas sa capacité. Les solveurs de contraintes utilisent des algorithmes de filtrage afin de réduire la taille de l'arbre de recherche et ainsi réduire le temps de résolution d'un problème. Je présenterai un nouvel algorithme de filtrage basé sur le raisonnement énergétique. Ce raisonnement, qui permet de filtrer fortement l'espace de recherche, a longtemps souffert d'algorithmes trop lents pour être utilisé en pratique. Je présenterai le premier test du raisonnement énergétique dont le temps d'exécution est sous-quadratique: O(n log^2 n). Je présenterai aussi l'algorithme de filtrage associé à ce test qui s'exécute en O(n^2 log n).
Biographie : Claude-Guy Quimper est professeur agrégé au département d'informatique et de génie logiciel à l’Université Laval. Ses recherches portent sur la programmation par contraintes, la recherche opérationnelle, la conception d'algorithmes et l'ordonnancement. Diplômé au doctorat de l'Université de Waterloo, il a été visiteur chez NICTA et stagiaire chez Microsoft Research. Il a fait un postdoctorat à Polytechnique Montréal sous la supervision du professeur Gilles Pesant. Il a travaillé dans l'industrie chez Oméga Optimisation, avec Louis-Martin Rousseau, et chez Google.
Bienvenue à tous!
