Apprentissage de bornes duales valides en programmation par contrainte : Décomposition lagrangienne amplifiée avec apprentissage auto-supervisé
(2025) JFPC 2025
Files
Actes_JFPC_PFIA2025.pdf
Open Access - Adobe PDF
- 14.46 MB
Details
- Authors
- Abstract
- Ce papier est un résumé de l’article "Learning Valid Dual Bounds in Constraint Programming : Boosted Lagran- gian Decomposition with Self-Supervised Learning" publié à AAAI 2025. La décomposition lagrangienne relaxe les problèmes d’optimisation en sous-problèmes plus simples pour améliorer les algorithmes de séparation et d’éva- luation en permettant le calcul d’une borne duale. Toute- fois, en programmation par contraintes, l’optimisation des multiplicateurs de Lagrange est coûteuse en raison de la complexité de résolution des sous-problèmes. Nous pro- posons une approche d’apprentissage auto-supervisé uti- lisant des réseaux de neurones pour générer ces multipli- cateurs et obtenir des bornes plus serrées. Cela réduit le nombre d’itérations nécessaires et accélère les solveurs. Notre méthode démontre une bonne généralisation sur des problèmes comme le sac à dos multidimensionnel.
- Affiliations
Citations
Bessa, S., Dabert, D., Bourgeat, M., Rousseau, L.-M., & Cappart, Q. (2025). Apprentissage de bornes duales valides en programmation par contrainte : Décomposition lagrangienne amplifiée avec apprentissage auto-supervisé. Actes des 20es Journées Francophones de Programmation par Contraintes, 87-89. https://hdl.handle.net/2078.5/272754 (Original work published 2025)