Apprentissage par renforcement appliqué à la résolution de problèmes de programmation par contraintes

Constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are the branching heuristics, designed to lead the search to the best solutions in a minimum amount of time. However, developing these heuristics is a time-consuming process that requires problem-specific expertise. This observation has motivated many efforts to use machine learning to learn efficient heuristics without expert intervention automatically. Although several generic variable-selection heuristics are available in the literature, the options for a generic value-selection heuristic are more scarce. In this paper, we propose to tackle this issue by introducing a generic learning procedure that can be used to obtain a value-selection heuristic inside a constraint programming solver. This has been achieved thanks to the combination of a deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network architecture. Experiments on graph coloring, maximum independent set, and maximum cut problems show that our generic framework is able to find better solutions close to optimality without requiring a large number of backtracks.

Résumé

La programmation par contraintes est connue pour être une approche à la fois efficace et versatile pour résoudre des problèmes combinatoires complexes. Dans un solveur de programmation par contraintes, une attention toute particulière doit être portée sur les heuristiques de branchement, qui permettent d’accélérer la recherche, en guidant celle-ci vers les meilleures solutions en un minimum de temps. Cependant, développer des heuristiques efficaces est une tâche complexe qui nécessite l’acquisition au préalable d’une expertise spécifique au problème. Cette observation a motivé de nombreux efforts pour utiliser de l’apprentissage automatique pour apprendre de manière générique des heuristiques de décision sans apport de connaissances extérieures. Bien que plusieurs heuristiques génériques de sélection de variables soient disponibles dans la littérature, les options pour une heuristique générique de sélection de valeurs sont plus rares ou moins étudiées. Dans cet article, nous proposons de résoudre ce problème en introduisant une procédure d’apprentissage générique qui peut être utilisée pour obtenir une heuristique de sélection de valeurs. Cette procédure est le fruit de la combinaison d’un algorithme d’apprentissage par renforcement appelé deep Q-learning, d’un signal de récompense personnalisé et d’une architecture de réseau neuronal hétérogène de type graph neural network. Des expériences sur trois classes distinctes de problèmes combinatoires permettent de valider expérimentalement la capacité de notre approche à apprendre des heuristiques performantes capables de trouver dans un temps restreint des solutions de bonnes qualités.