Programme de Doctorat en informatique
Département d’informatique et de génie logiciel
Faculté des sciences et de génie
Présentation orale de la proposition de projet de recherche
(IFT-8003)
De
Frédéric Berthiaume
Le vendredi 20 septembre 2024 à 9 h
Local 2546, Pavillon Adrien Pouliot
Augmentation du filtrage des contraintes globales
à l’aide de la relaxation Lagrangienne
Membres du comité d’encadrement
Claude-Guy Quimper, Ph.D. (Directeur de recherche)
Département d’informatique et de génie logiciel
Mikael Rönnqvist, Ph.D. (Examinateur)
Département de génie mécanique
Pascal Tesson, Ph.D. (Examinateur)
Département d’informatique et de génie logiciel
Résumé
Au cœur de la programmation par contraintes se trouvent les algorithmes de filtrage associés à des contraintes. Ces algorithmes retirent du domaine des variables des valeurs incohérentes avec la relation imposée par la contrainte. Il existe des contraintes pour lesquelles la relation imposée peut être écrite sous la forme d’un programme linéaire. On peut concevoir des algorithmes de filtrage basés sur les coûts réduits des variables de ce programme linéaire. Combinés à une relaxation Lagrangienne, il a été montré que les multiplicateurs de Lagrange sous-optimaux sont meilleurs pour faire du filtrage par coût réduit. Nous poussons cette idée en détériorant les multiplicateurs de Lagrange de manière à augmenter le filtrage. Nous avons déjà eu des résultats prometteurs avec la contrainte AuPlusNValeur. Nous allons appliquer cette méthode à la contrainte SacÀDos. L’objectif est de généraliser cette procédure d’altérations locales de multiplicateurs de Lagrange et l’adapter à de nouvelles contraintes.
Note : La présentation sera donnée en français.
Bienvenue à tous !
