Description du sujet de thèse

La programmation linéaire mixte en nombres entiers (MILP) est un ensemble de technologies qui sous-tendent une grande partie de la logistique et de la production modernes. La méthode du simplexe est l'un des composants algorithmiques clés de tout logiciel MILP. Cet algorithme est connu pour sa rapidité en pratique, mais le cadre de l'analyse du pire cas ne permet pas d'expliquer cette observation. Différents cadres d'analyse ont été proposés pour expliquer les bonnes performances de l'algorithme, chacun présentant ses propres forces et faiblesses. La thèse de doctorat contribuera à trouver des bornes supérieures plus solides et plus rigoureuses pour le temps d'exécution de la méthode du simplexe.

Contexte de travail

Le candidat utilisera une approche mathématique basée sur la preuve. En s'appuyant sur les cadres théoriques de pointe de l'analyse lissée et des hypothèses d'entrée déterministes, le candidat améliorera d'abord les théorèmes connus les plus solides dans ce domaine. Ensuite, la thèse formulera un successeur à ces cadres. Ce nouveau cadre s'appuiera sur une compréhension nouvelle des hypothèses de fonctionnement des logiciels MILP modernes.
En raison de la durée limitée du contrat, nous attendons du candidat une bonne préparation pour les recherches à mener.
Exigences:
- Solide expérience en démonstrations mathématiques et en analyse d'algorithmes.
- Solide expérience en théorie des probabilités et en analyse convexe.
- Solide expérience en géométrie discrète et/ou en polyèdres convexes.

Contraintes et risques

Idéalement, ces exigences sont justifiées par des publications antérieures ou un mémoire de master. Une expertise en programmation linéaire (en nombres entiers mixtes), en méthode du simplexe et en hypothèses de fonctionnement attendues serait un atout.