Annonce de th
Forum 'Emplois' - Sujet créé le 2011-04-01
Sujet de thèse proposé à Lille
Encadrants : François Clautiaux (hdr) et El-Ghazali Talbi (professeur)
La programmation mathématique est un outil très puissant pour résoudre des problèmes d'optimisation complexes. Les progrès réalisés par les « solvers » génériques permettent désormais d'envisager la résolution de problèmes de grande taille. Pour les plus durs, on a souvent recours à des reformulations qui permettent d'améliorer les résultats au prix d'une augmentation importante de la taille des modèles (exponentielle, ou pseudo-polynomiale).
Une des techniques les plus populaires pour résoudre des programmes linéaires de grande taille est la décomposition de Dantzig et Wolfe (méthode classique de génération de colonnes). Une autre possibilité offerte par la puissance des solvers linéaires est d'entrer des modèles dont la taille est pseudo-polynomiale. Ces méthodes [3] ont permis de résoudre des problèmes de tournées de véhicules de manière spectaculairement plus rapide que les méthodes basées sur la génération de colonnes.
Ces méthodes atteignent leurs limites lorsque la valeur des données devient trop importante. Cependant, les idées sous-jacentes peuvent être utilisées dans la production d'heuristiques ou de méta-heuristiques [4] très puissantes basées sur ces modèles (voir [2] par exemple). Les techniques de réoptimisation et de génération d'un ensemble de colonnes à chaque étape améliorent considérablement la performance de l'algorithme de génération de colonnes [1]. La communauté d'optimisation multi-objectif a développé de nombreux outils pour générer des ensembles diversifiés de solutions : l'utilisation de ces outils dans le cadre de la génération de colonnes est à étudier. Une autre piste d'amélioration de ces méthodes est d'avoir recours au parallélisme, qui permet de prendre efficacement en charge des problème dont la taille dépend d'une grande constante.
L'objectif principal de la thèse est de mettre au point des méthodes hybrides reposant sur des reformulations de programmes linéaires, sur les méta-heuristiques et/ou le parallélisme. Le travail portera sur différentes techniques de reformulation, et la possibilité de les intégrer efficacement dans des frameworks méta-heuristiques, et sur leurs potentialités de parallélisation. Le but est d'obtenir des résultats pratiques très efficaces, mais aussi des garanties théoriques.
Les techniques mises au point seront validées principalement sur des problèmes liés à la logistique et au transport (tournées de véhicules, emploi du temps, optimisation d'entrepôt et/ou conditionnement).
L'équipe d'accueil
L'équipe DOLPHIN est spécialisée dans la résolution de problèmes d'optimisation à l'aide de méthode collaboratives parallèles. Elle comporte des compétences en programmation mathématique, en optimisation multi-objectif et dans les méta-heuristiques parallèles.
Les compétences demandées
On demandera au candidat d'avoir des connaissances avancées en algorithmique, optimisation combinatoire et des connaissances en programmation mathématique.
Bibliographie
[1] N. Touati Moungla, Performances improvement of the column generation algorithm: application to vehicle routing problems, thèse de doctorat, 2010.
[2] C. Joncour, S. Michel, R. Sadykov, D. Sverdlov, F. Vanderbeck, Column Generation based Primal Heuristics, Electronic Notes in Discrete Mathematics, Volume 36, Pages 695-702, 2010
[3] R. Macedo, C. Alves, J. Valério de Carvalho, F. Clautiaux, S. Hanafi, Solving exactly the vehicle routing problem with time windows and multiple routes using a pseudo-polynomial model, revised for European Journal of Operational Research, 2010
[4] E.G. Talbi, Metaheuristics: From Design to Implementation, Wiley, 2009
Encadrants : François Clautiaux (hdr) et El-Ghazali Talbi (professeur)
La programmation mathématique est un outil très puissant pour résoudre des problèmes d'optimisation complexes. Les progrès réalisés par les « solvers » génériques permettent désormais d'envisager la résolution de problèmes de grande taille. Pour les plus durs, on a souvent recours à des reformulations qui permettent d'améliorer les résultats au prix d'une augmentation importante de la taille des modèles (exponentielle, ou pseudo-polynomiale).
Une des techniques les plus populaires pour résoudre des programmes linéaires de grande taille est la décomposition de Dantzig et Wolfe (méthode classique de génération de colonnes). Une autre possibilité offerte par la puissance des solvers linéaires est d'entrer des modèles dont la taille est pseudo-polynomiale. Ces méthodes [3] ont permis de résoudre des problèmes de tournées de véhicules de manière spectaculairement plus rapide que les méthodes basées sur la génération de colonnes.
Ces méthodes atteignent leurs limites lorsque la valeur des données devient trop importante. Cependant, les idées sous-jacentes peuvent être utilisées dans la production d'heuristiques ou de méta-heuristiques [4] très puissantes basées sur ces modèles (voir [2] par exemple). Les techniques de réoptimisation et de génération d'un ensemble de colonnes à chaque étape améliorent considérablement la performance de l'algorithme de génération de colonnes [1]. La communauté d'optimisation multi-objectif a développé de nombreux outils pour générer des ensembles diversifiés de solutions : l'utilisation de ces outils dans le cadre de la génération de colonnes est à étudier. Une autre piste d'amélioration de ces méthodes est d'avoir recours au parallélisme, qui permet de prendre efficacement en charge des problème dont la taille dépend d'une grande constante.
L'objectif principal de la thèse est de mettre au point des méthodes hybrides reposant sur des reformulations de programmes linéaires, sur les méta-heuristiques et/ou le parallélisme. Le travail portera sur différentes techniques de reformulation, et la possibilité de les intégrer efficacement dans des frameworks méta-heuristiques, et sur leurs potentialités de parallélisation. Le but est d'obtenir des résultats pratiques très efficaces, mais aussi des garanties théoriques.
Les techniques mises au point seront validées principalement sur des problèmes liés à la logistique et au transport (tournées de véhicules, emploi du temps, optimisation d'entrepôt et/ou conditionnement).
L'équipe d'accueil
L'équipe DOLPHIN est spécialisée dans la résolution de problèmes d'optimisation à l'aide de méthode collaboratives parallèles. Elle comporte des compétences en programmation mathématique, en optimisation multi-objectif et dans les méta-heuristiques parallèles.
Les compétences demandées
On demandera au candidat d'avoir des connaissances avancées en algorithmique, optimisation combinatoire et des connaissances en programmation mathématique.
Bibliographie
[1] N. Touati Moungla, Performances improvement of the column generation algorithm: application to vehicle routing problems, thèse de doctorat, 2010.
[2] C. Joncour, S. Michel, R. Sadykov, D. Sverdlov, F. Vanderbeck, Column Generation based Primal Heuristics, Electronic Notes in Discrete Mathematics, Volume 36, Pages 695-702, 2010
[3] R. Macedo, C. Alves, J. Valério de Carvalho, F. Clautiaux, S. Hanafi, Solving exactly the vehicle routing problem with time windows and multiple routes using a pseudo-polynomial model, revised for European Journal of Operational Research, 2010
[4] E.G. Talbi, Metaheuristics: From Design to Implementation, Wiley, 2009