Convergence accélérée de la Décomposition Lagrangienne pour la Planification Automatique
(2025) JFPC 2025
Files
Actes_JFPC_PFIA2025.pdf
Open Access - Adobe PDF
- 14.46 MB
Details
- Authors
- Abstract
- La décomposition lagrangienne est une méthode de pro- grammation linéaire en nombres entiers qui exploite la structure d’un problème pour construire des sous- problèmes indépendants. La résolution de ces sous- problèmes procure une borne à l’optimalité sur le problème original. La qualité de cette borne peut être optimisée par des itérations de sous-gradients sur un vecteur de multipli- cateurs. On compte plusieurs contributions qui transposent ces principes en programmation par contraintes. Une ap- proche récente, introduite par Bessa et al. (2025) permet d’inférer une meilleure borne grâce à un modèle d’appren- tissage. Notre projet de recherche vise à trouver des trans- positions de cette méthode vers d’autres domaines de réso- lution de problèmes combinatoires et d’en évaluer l’apport. Une première discipline identifiée est la planification auto- matique. Ce papier montre nos avancées préliminaires pour améliorer une méthode existante de décomposition lagran- gienne en planification. Nos premiers résultats témoignent d’une avancée des performances avant d’avoir incorporé l’apprentissage dans notre méthodologie.
- Affiliations
Citations
Barral, H., Cappart, Q., Huguet, M.-J., & Thiébaux, S. (2025). Convergence accélérée de la Décomposition Lagrangienne pour la Planification Automatique. Actes des 20es Journées Francophones de Programmation par Contraintes, 128-133. https://hdl.handle.net/2078.5/272756 (Original work published 2025)