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é.