Sujet De These 1

L'objectif de la thèse est de développer des méthodologies pour résoudre des problèmes d'optimisation combinatoire de grande taille soumis aux aléas. Le travail se concentrera sur leur application à des problèmes de partitionnement avant de généraliser les méthodes à d'autres problèmes.

Les problèmes de partitionnement sont aujourd'hui bien résolus pour des fonctions objectif standard et des instances de taille moyenne. Lorsque l'on considère des contraintes complexes pour la création des parties, ou quand la taille des instances devient plus importante, les techniques standard de programmation linéaire en nombres entiers ne permettent plus de résoudre efficacement ces problèmes. Lorsque l'on considère en plus la gestion de l'incertitude, la taille des modèles devient beaucoup trop importante pour autoriser une résolution frontale. L'objectif de la thèse est de proposer des méthodes qui permettent de résoudre en pratique de tels problèmes.

Dans un premier temps, il s'agira de proposer des méthodes pour résoudre la version déterministe des problèmes considérés. Les pistes à étudier concerneront les méthodes de décomposition (Dantzig et Wolfe principalement) et les méthodes d'agrégation/désagrégation. Ces dernières méthodes ont fait leur preuve dans des problèmes de tournées et des problèmes de conditionnement. Leur application aux problèmes de partitionnement posent des difficultés importantes qu'il faudra lever au cours de la thèse.

Dans un deuxième temps, on cherchera à étendre au cas robuste les résultats obtenus dans la première partie de la thèse. En particulier, l'application des techniques d'agrégation aux modèles robuste sera comparée aux techniques de génération différée de contraintes.

Les compétences demandées pour le candidat sont la programmation linéaire, l'optimisation combinatoire, et la programmation orientée objet. Une expérience dans les techniques de décomposition de programmes linéaires est un plus mais n'est pas requise.

Contact :

francois.clautiaux@math.u-bordeaux.fr
pierre.pesneau@math.u-bordeaux.fr