Thèse (urgent) : Résolution de problèmes d'ordonnancement par le couplage de la RO et du ML

Suite à un désistement pour raison personnelle du candidat, nous nous retrouvons à devoir pourvoir à nouveau et très rapidement l'offre de thèse ci-dessous.

Si vous êtes intéressés, n'hésitez pas à prendre contact avec nous dans les plus brefs délais et à candidater avant le 1er décembre 2024.

Vincent T'kindt (tkindt@univ-tours.fr)

Romain Raveaux (romain.raveaux@univ-tours.fr)

Jean-Paul Chemla (jean-paul.chemla@univ-tours.fr)

---------------------------------------------------------------

Une bourse de thèse à temps plein au Laboratoire d'Informatique Fondamentale et Appliquée (LIFAT) à Tours est proposée pour la rentrée 2024. La thèse portera sur le couplage de techniques de machine learning et de recherche opérationnelle pour la résolution de problèmes d'ordonnancement. Il s'agit donc d'une thèse de doctorat en RO à l'interface avec le domaine du machine learning.

Vous trouverez plus d'information ci-dessous (incluant la procédure pour candidater).

Titre : Résolution de problèmes d?ordonnancement par le couplage de la Recherche Opérationnelle et du Machine Learning

Directeur de thèse : 

Vincent T?kindt  - email : tkindt@univ-tours.fr

Jean-Paul Chemla - email : chemla@univ-tours.fr

Romain Raveaux - email : romain.raveaux@univ-tours.fr

Mots clés : ordonnancement, Recherche Opérationnelle, Machine Learning.

1. Equipe d?accueil

Laboratoire d?Informatique Fondamentale et Appliquée de Tours (EA 6300 LIFAT) ? Equipe Recherche Opérationnelle, Ordonnancement et Transport et équipe Reconnaissance des Formes et Analyse d?Images (RFAI).

2. Descriptif de la Thèse 

Dans ce sujet nous nous intéressons à la résolution de problèmes d?ordonnancement difficiles, au sens de la théorie de la complexité, pour lesquels nous souhaitons proposer de nouveaux algorithmes heuristiques tirant partie des outils de la Recherche Opérationnelle et du machine learning. Il s?agit d?une thèse en Recherche Opérationnelle et pour laquelle des compétences en machine learning seront nécessaires/développées.

L?utilisation de techniques de d?apprentissage au sein d?algorithmes d?optimisation est apparue ces dernières années et un tour d?horizon en est présenté dans [1]. Considérons tout d?abord le cas des algorithmes exactes. Lodi and Zaperllon ([2]) présentent un état de l?art sur l?utilisation de l?apprentissage au sein des méthodes arborescentes pour la résolution de programmes mathématiques. Il s?agit alors soit d?apprendre les meilleurs paramètres du solveur, soit d?apprendre comment guider efficacement la recherche arborescente. L?utilisation de l?apprentissage automatique au sein d?heuristiques a fait l?objet de plusieurs publications à chaque fois sur des problèmes particuliers. Ces études sont très diverses et portent aussi bien sur l?apprentissage de stratégies de diversification que sur la sélection automatique d?heuristiques pour résoudre une instance donnée. Certaines portent également sur l?utilisation d?un prédicteur pour directement construire une solution au problème : c?est notamment le cas de l?algorithme proposé par Silver et al. pour résoudre le jeu de GO ([6]). Récemment de premières études ont porté sur l?utilisation de techniques d?apprentissage pour guider des heuristiques de type Recherche Locale, notamment sur des problèmes de transport (e.g. [3, 4, 5]). Il s?agit là de premiers travaux qui montrent l?impact positif d?un tel couplage de techniques.

Dans cette thèse, les travaux menés vont porter sur deux axes complémentaires :

• Utiliser des techniques comme l'optimisation Bayesienne ([7]) pour déterminer le paramétrage d?heuristiques,
• Utiliser des techniques de Deep Learning et de Reinforcement Learning pour guider l?exploration d?un espace de solutions (qui peut être le voisinage d?une solution courante, ou un ensemble de solutions ayant une sous-séquence commune).

Ces deux points sont liés puisqu?il s?agira de coupler apprentissage des paramètres et guidage dans un espace de solutions. Le point novateur, par rapport à la littérature, est que nous mettrons l?accent sur l?utilisation de techniques d?apprentissage sans features.

Les travaux menés porteront sur la résolution de problèmes d?ordonnancement NP-difficiles et les algorithmes développés seront comparés aux meilleures heuristiques de la littérature. Nous considérerons deux problèmes d?ordonnancement très différents à plusieurs titres : un problème plutôt « académique » et pour lequel il existe déjà des heuristiques très performantes et un second plutôt « appliqué » et donc beaucoup difficile à résoudre par une heuristique. Nous essayerons de démontrer qu?il est possible de coupler apprentissage et Recherche Opérationnelle pour contribuer à la résolution de ces deux types de problèmes.

3. Comment candidater ? 

Il suffit de prendre contact avec les trois encadrants et d?envoyer : un CV, une lettre de motivation, vos relevés de notes de master (ou équivalent). Vous pouvez y joindre des lettres de recommandation.

Les compétences minimales recherchées sont :

• Une bonne connaissance des outils de la Recherche Opérationnelle,
• Connaître les notions de base de la théorie de la complexité,
• Être curieux et passionné par la recherche,
• Savoir développer dans un langage de programmation de type C ou C++.

Avoir une bonne connaissance des outils du Machine Learning sera apprécié.

Références bibliographiques 

[1] Bengio, Y., Lodi, A. Prouvost, A. (2021). Machine Learning for Combinatorial Optimization: a Methodological Tour d?Horizon, European Journal of Operational Research, 290:405-421.

[2] Lodi, A., and Zaperllon, G. (2017). On learning and branching: a survey, TOP ? An official journal of the Spanish Society  of Statistics and Operations Research, 25(2): 207-236.

[3] Arnold, F., Sorensen, K. (2019). What makes a VRP solution good? The generation of problem-specific knowledge for heuristics. Computer and Operations Research, 106:280-288.

[4] Gauthier, J.B., Irnich, S. (2018). Machine learning to guide sequential search ? Part II. 7th International workshop on freight transportation and logistics (Odysseus?18), Cagliary (Italie).

[5] Arnold, F., Santana, I., Sorensen, K., Vidal, T. (2021). PILS: Exploring high order neighborhoods by pattern mining and injection. Pattern Recognition, 116:107957.

[6] Silver, D., Schrittwieser, J., Simonvan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T. Hassabis, D. (2017). Mastering the game of Go without human knowledge, Nature, 550 :354-359.

[7] Wu, J., Chen, X.-Y., Zhang, H., Xiong, L.D, Lei, H., Deng, S.-H. (2019). Hyperparameter optimization for machine learning models based on Bayesian optimization. Journal of Electronic Science and Technology, 17(1):26-40.