Apprentissage par renforcement d'heuristiques de branchement en programmation par contraintes

La résolution de problèmes combinatoires en programmation par contraintes (CP) se fait par énumération des solutions. Cette procédure exhaustive est très coûteuse et la conception d'heuristiques de branchement visant à accélérer l'exploration de l'espace des solutions est souvent indispensable. Néanmoins, la conception d'heuristiques dédiées est un processus long, nécessitant une expertise et ne se généralise pas à un large nombre de problèmes différents. Ce constat a motivé l'utilisation de modèles d'apprentissage machine pour automatiquement apprendre des heuristiques performantes sans expertise humaine. Ces modèles entraînés par apprentissage par renforcement (RL) peuvent alors être intégrés à des solveurs de programmation par contraintes au sein d'une méthode de recherche simple comme la fouille en profondeur pour explorer systématiquement l'espace des solutions. Inspiré par les récents développement du système AlphaZero, un algorithme générique combinant recherche arborescente et apprentissage par renforcement, nous proposons un nouvel algorithme de résolution de problèmes combinatoires combinant les avantages de la programmation par contraintes avec la possibilité d'apprendre automatiquement une stratégie d'exploration de l'espace des solutions.