Le 19/02/2024 par tkindt :
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 :
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 :
Avoir une bonne connaissance des outils du Machine Learning sera apprécié.
La date limite d?envoie des candidatures est fixée au 20 avril 2024.
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.
