Offre de thèse
Optimisation combinatoire et apprentissage automatique
Date limite de candidature
30-04-2024
Date de début de contrat
01-10-2024
Directeur de thèse
NAGIH Anass
Encadrement
Co-encadrement Université de Lorraine (LORIA et LCOMS) Collaboration avec l'Université de Luxembourg dans le cadre d'un projet ANR/FNR Déroulement sur le campus de Metz, laboratoires LCOMS et LORIA
Type de contrat
école doctorale
équipe
contexte
Projet sur financement ANRspécialité
Informatiquelaboratoire
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Mots clés
Optimisation combinatoire, Programmation linéaire, Apprentissage automatique, Génération de colonnes, Problèmes de transport
Détail de l'offre
L'utilisation de techniques d'apprentissage automatique pour améliorer les performances d'algorithmes et heuristiques pour l'optimisation combinatoire se propage de plus en plus. Parmi les méthodes pour résoudre les problèmes combinatoires, les algorithmes utilisant la génération de colonnes ont fait leur preuve sur de nombreux problèmes notamment les problèmes de tournées de véhicules. Par rapport à d'autres méthodes, notamment les méta-heuristiques, on relève moins d'études portant sur l'amélioration des algorithmes utilisant la génération de colonnes par l'apprentissage automatique. Pourtant, leur nature itérative et reposant sur des structures liées à la programmation linéaire ouvre la voie à de nombreuses possibilités. L'objectif de cette thèse est de proposer des méthodes d'apprentissage automatique pour améliorer les algorithmes de génération de colonnes. Les méthodes proposées seront appliquées à des problèmes rencontrés en apprentissage automatique et en optimisation combinatoire. L'utilisation du calcul haute- performance sera également envisagée pour permettre la résolution de problèmes de grandes tailles.
Keywords
Combinatorial optimization, Linear programming, Machine learning, Column generation, Transportation problems
Subject details
The use of machine learning techniques to improve the performance of algorithms and heuristics for combinatorial optimisation is becoming increasingly popular. Among the methods for solving combinatorial problems, algorithms using column generation have proven to be successful on many problems, including vehicle routing problems. Compared to other methods, notably meta-heuristics, there are fewer studies on the improvement of algorithms using column generation through machine learning. However, their iterative nature and reliance on linear programming structures opens up many possibilities. The objective of this thesis is to propose machine learning methods to improve column generation algorithms. The proposed methods will be applied to problems encountered in machine learning and combinatorial optimisation. The use of high performance computing will also be considered to allow the solution of large size problems.
Profil du candidat
- Proposal and implementation of decomposition algorithms of the column generation type for problems related to machine learning
- Use of machine learning methods and high performance computing to boost the proposed decomposition algorithms
- Strong algorithmic and programming skills (especially on efficiency issues of algorithms and programs)
- Proficiency in a programming language (C++, Julia, Python, etc.)
Candidate profile
- Proposal and implementation of decomposition algorithms of the column generation type for problems related to machine learning
- Use of machine learning methods and high performance computing to boost the proposed decomposition algorithms
- Strong algorithmic and programming skills (especially on efficiency issues of algorithms and programs)
- Proficiency in a programming language (C++, Julia, Python, etc.)
Référence biblio
L. Accorsi, A. Lodi, and D. Vigo. “Guidelines for the Computational Testing of Machine Learning Approaches to Vehicle Routing Problems”. In: Operations Research Letters 50 (2022), pp. 229–234.