Apprentissage profond pour l'optimisation et la satisfaction de contraintes – DELCO

L'objectif du projet est d'utiliser des techniques établies d'apprentissage par imitation et par renforcement pour définir une nouvelle catégorie de solveurs capables d'apprendre. Nous commencerons par générer de grandes quantités de données supervisées en utilisant des algorithmes Monte-carlo comme MCTS, et nous utiliserons ces données pour entraîner un réseau de neurones à imiter les décisions de branchement prises par MCTS, mais sans avoir a dérouler les très nombreuses simulations nécessaire à MCTS. Nous pouvons également utiliser les algorithmes d'apprentissage par renforcement comme REINFORCE pour améliorer la stratégie de résolution avec les données récoltées pendant la résolution du problème.

Pas de résultats pour l'instant.

Un solveur MIP basé sur SCIP capable d'apprendre des mécanismes de résolutions efficaces à partir de données historiques et de données récoltées pendant la résolution du problème.

1. Fréchet Mean Computation in Graph Space through Projected Block Gradient Descent. Boria, N., Negrevergne, B., & Yger, F. (2020). European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN).
2. The Minimum Edit Arborescence Problem and Its Use in Compressing Graph Collections. Gnecco, L., Boria, N., Bougleux, S., Yger, F., & Blumenthal, D. B. (2021). International Conference on Similarity Search and Applications.
3. Monte Carlo Graph Coloring. Cazenave, T., Negrevergne, B., & Sikora, F. (2020). Monte Carlo Search, IJCAI Workshop.
4. Deep Reinforcement Learning for Morpion Solitaire. Doux, B., Negrevergne, B., & Cazenave, T. (2021). Advances in Computer Games.
5. On the expressivity of bi-Lipschitz normalizing flows. Verine, A., Negrevergne, B., Rossi, F., & Chevaleyre, Y. (2021). ICML Workshop on Invertible Neural Networks, Normalizing Flows, and Explicit Likelihood Models.

Ce projet vise à concevoir une nouvelle génération de solveurs de programmation par contraintes plus généraux et plus performants. Pour y parvenir, nous nous appuieront sur les progrès récents effectués dans le domaine de l'apprentissage automatique (deep learning) et de l'apprentissage par renforcement.

Plus précisément, notre objectif est de développer une méthodologie pour apprendre des heuristiques de branchements apprises, capables de prendre des décisions pertinentes tout au long de l'exploration de l'espace de recherche. Pour atteindre cet objectif, nous utiliserons des réseaux de neurones convolutionels (CNNs) afin de modéliser les relations complexes qui peuvent exister entre l'état du problème en cours de résolution, et la variable de branchement optimale. Nous nous appuieront également sur l'apprentissage par renforcement pour entraîner les heuristiques en utilisant des récompenses éparses comme le temps d'exécution ou la taille de l'arbre de recherche. Combinées, ces deux techniques permettront de guider l'exploration rapidement vers les solutions au problème de satisfaction de contraintes.

Dans ce projet, nous évalueront le bien fondé de cette approche sur un ensemble de tâches de différentes natures. Nous commenceront par des problèmes représentés sous forme de grille puisque ces derniers peuvent être directement traités dans un CNNs classique. Puis nous explorerons des problèmes représentables sous forme de graphes, qui peuvent être abordés à l'aide de plongements de graphes.

Un deuxième axe de recherche visera à combiner les heuristiques apprises, avec différentes stratégies d'exploration. Tout d'abord, avec de simples stratégies gloutonnes, puis avec des algorithmes de recherche arborescente et enfin des solveurs de contraintes issus de l'état de l'art. Nous serons particulièrement attentifs aux possibles synergies entre les techniques de raisonnement (e.g. propagation de contraintes) et les techniques d'apprentissage automatique.

Ce projet portera également une attention particulière à la généralité et a la robustesse des approches développées. Nous tenterons d'adapter plusieurs techniques issues de l'apprentissage automatique traditionnellement utilisées pour produire des modèles plus généraux et plus robustes. En particulier nous nous intéresserons à la génération d'instances difficiles, ainsi qu'à la mise en oeuvre des réseaux antagonistes (generative adversarial networks) pour les problèmes abordés dans le cadre de ce projet. Cela nous permettra d'apprendre des heuristiques plus générales, plus robustes et performante dans les pires cas.

Le succès de ce projet repose en grande partie sur une méthodologie expérimentale solide. En effet, les compétences d'un ingénieur seront mobilisées pour mettre en place une plate-forme de tests entièrement automatisée. Cette plate-forme sera utilisée tout au long du projet pour obtenir une évaluation fiable des performances de notre approche, et pour produire des éléments de compréhension importants pour les aspects les plus fondamentaux.

En cas de succès, nous pouvons espérer des percées scientifiques importantes. Par exemple:
- Le développement de solveurs plus généraux. En particulier, de solveurs dont l'efficacité ne dépend pas de la manière d'encoder un problème sous forme de variables et de contraintes. Cela permettra de rendre les solveurs de programmation par contraintes plus accessibles aux utilisateurs novices.
- Des solveurs capables d'utiliser conjointement les techniques de raisonnement logique et d'apprentissage statistique. Cette perspective ouvre la voie à un nouveau paradigme pour la conception de solveurs.
- Des solveurs hybrides capables d'exploiter simultanément la puissance de calcul des architectures GPU (pour l'inférence dans les réseaux de neurones) et cette des CPU (pour la recherche arborescente et la propagation de contraintes).
- De nouvelles techniques d'apprentissages issues des travaux récents sur les réseaux antagonistes.