Vers une représentation générique des problèmes combinatoires à des fins d'apprentissage

Les dernières années ont vu un intérêt croissant pour l’utilisation d’approches basées sur l’apprentissage pour résoudre des problèmes combinatoires, soit de manière autonome, soit en conjonction avec des algorithmes d’optimisation traditionnels. Dans les deux scénarios, un défi réside dans l’encodage des problèmes combinatoires en une structure compatible avec l’algorithme d’apprentissage donné. De nombreux travaux existants ont proposé des représentations spécifiques aux problèmes, souvent sous la forme d’un graphe, pour tirer parti des avantages des réseaux neuronaux sur graphes. Cependant, ces approches manquent de généralité, car la représentation ne peut pas être facilement transférée d’un problème combinatoire à un autre. Bien que des tentatives aient été faites pour combler cette lacune, elles offrent encore seulement une généralité partielle. En réponse à ce défi, ce mémoire plaide en faveur de progrès vers une représentation entièrement générique des problèmes combinatoires pour les approches basées sur l’apprentissage. L’approche que nous proposons consiste à construire un graphe en décomposant toute contrainte d’un problème combinatoire en un arbre syntaxique abstrait et en exprimant les relations (par exemple, une variable impliquée dans une contrainte) à travers les arêtes. De plus, nous introduisons une architecture de réseau neuronal sur graphe capable d’apprendre efficacement à partir de cette représentation. L’outil fourni fonctionne sur des problèmes combinatoires exprimés dans le format XCSP3, un format universel de modélisation de problèmes de programmation par contraintes et largement utilisé dans la communauté scientifique. Notre approche permet de gérer toutes les contraintes disponibles dans la compétition mini-track de 2023. Les résultats expérimentaux sur quatre problèmes combinatoires démontrent que notre architecture atteint des performances comparables à celles des architectures dédiées tout en conservant la généralité.

Abstract

In recent years, there has been a growing interest in using learning-based approaches for solving combinatorial problems, either in an end-to-end manner or in conjunction with traditional optimization algorithms. In both scenarios, the challenge lies in encoding the targeted combinatorial problems into a structure compatible with the learning algorithm. Many existing works have proposed problem-specific representations, often in the form of a graph, to leverage the advantages of graph neural networks. However, these approaches lack generality, as the representation cannot be easily transferred from one combinatorial problem to another one. While some attempts have been made to bridge this gap, they still offer a partial generality only. In response to this challenge, this thesis advocates for progress toward a fully generic representation of combinatorial problems for learning-based approaches. The approach we propose involves constructing a graph by breaking down any constraint of a combinatorial problem into an abstract syntax tree and expressing relationships (e.g., a variable involved in a constraint) through the edges. Furthermore, we introduce a graph neural network architecture capable of efficiently learning from this representation. The tool provided operates on combinatorial problems expressed in the XCSP3 format, handling all the constraints available in the 2023 mini-track competition. Experimental results on four combinatorial problems demonstrate that our architecture achieves performance comparable to dedicated architectures while maintaining generality.