Séminaire départemental – Relaxation lagrangienne en programmation par contraintes appliquée au problème du commis voyageur

Visioconférence: Zoom (https://tinyurl.com/1a86yh1n)

Résumé: La relaxation lagrangienne est une technique d’optimisation efficace et largement utilisée en optimisation. Dans le contexte de la programmation par contraintes, il est possible d’en faire usage en la combinant à une technique de filtrage spécifique basée sur la notion de coût. En particulier, les algorithmes de filtrage de l’état de l’art pour la contrainte WeightedCircuit, qui encode le problème du commis voyageur (traveling salesman problem, TSP), sont basés sur cette approche. Dans ce séminaire, nous introduirons l’ensemble des notions permettant de comprendre chacun des mots des précédentes phrases de ce résumé. Puis, nous proposerons une nouvelle approche modifiant localement les multiplicateurs de Lagrange dans le but d’augmenter le nombre de valeurs filtrées. En appliquant cette dernière au filtrage de la contrainte WeightedCircuit sur des instances du TSP, un gain significatif sur le temps de résolution et la taille de l’espace de recherche est obtenu par rapport à l’état de l’art.