Vendredi 1er mars 2024

Augmentation du filtrage de la contrainte AuPlusNValeur à l’aide d’altérations locales des multiplicateurs de Lagrange
Frédéric Berthiaume
Doctorant au laboratoire de programmation par contraintes, département d’informatique et de génie logiciel

Heure: 13h30
Local: PLT-2551

Résumé: En se basant sur deux techniques éprouvées, une nouvelle idée d’algorithme est testée en programmation par contraintes. Au coeur 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 entre les variables imposée par la contrainte. Un algorithme de filtrage d’une contrainte basé sur le filtrage par coût réduit utilise les coûts réduits du programme linéaire encodant la contrainte pour filtrer les valeurs du domaine des variables. Combiné à 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. Un algorithme pour la contrainte CircuitPondéré a poussé cette idée en altérant localement des multiplicateurs de Lagrange optimaux pour accentuer le filtrage de la contrainte.

Nous poussons cette idée encore plus loin, mais sur une différente contrainte. La contrainte AuPlusNValeur a plusieurs applications entre autres pour le problème de localisation et cartographie simultanée (SLAM) et la couverture d’aire pour des entreprises. Satisfaire la contrainte AuPlusNValeur est NP-difficile. Il existe déjà un algorithme de relaxation Lagrangienne pour la contrainte, mais aucun algorithme d’altérations locales. Nous avons rajouté une étape dédiée aux altérations locales des multiplicateurs Lagrange. Cette étape utilise une deuxième relaxation Lagrangienne qui tient compte des coûts réduits. Nous avons testé l’algorithme sur le problème des reines dominantes et le problème p-median. Sur le problème des reines dominantes, l’algorithme d’altérations locales a accéléré le temps pour trouver une solution de 71% en moyenne. Sur le problème p-median, il y avait trois classes de problèmes. Sur les deux premières, l’algorithme proposé a accéléré le temps de 33% et 8% en moyenne. Sur la dernière, l’algorithme proposé a trouvé 13 meilleures solutions que l’algorithme original sur les 30 instances du banc d’essai.