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.

Abstract

Discrete optimization with Constraint Programming (CP) requires an expensive enumeration of the whole solution space. In order to be tractable, CP uses carefully crafted branching heuristics to speed up the search. Designing these heuristics is time-consuming, requires a human expertise and is very problem-specific. This observation has motivated the use of Machine Learning models to automatically learn efficient heuristics from raw data, without human supervision. Models trained by Reinforcement Learning (RL) can then be integrated within CP solvers and used in combination with a simple search algorithm such as a Depth-First Search (DFS).We propose a new algorithm to solve combinatorial problems within the CP framework, inspired by the recent advent of AlphaZero, a generic hybrid method featuring a tree search algorithm with Reinforcement Learning models. This method combines all the benefits of CP with the ability to directly learn efficient heuristics directly from raw interactions with the problem to solve.