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

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.