Convergence accélérée de la Décomposition Lagrangienne pour la Planification Automatique

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.