Sujet De These Decoupe
Contexte industriel
Dans le cadre de ses multiples activités, la société Saint-Gobain est confrontée à différents problèmes de découpe de matière première. Ces problèmes peuvent être en deux ou trois dimensions, et sont soumis à des contraintes pratiques différentes en fonction de l'application. Les méthodes issues de l'état de l'art ne sont pas aujourd'hui suffisantes pour les résoudre de manière satisfaisante.
Contexte académique
Les méthodes de programmation en nombres entiers sont aujourd'hui parmi les plus performantes pour la résolution de problèmes de découpe, notamment grâce aux formulations dites étendues et à des techniques de décomposition (Dantzig-Wolfe, Benders) qui permettent de gérer efficacement la taille exponentielle des modèles obtenus.
L'équipe Inria Realopt est spécialisée dans ces techniques de décomposition, et a notamment développé des algorithmes génériques pour mettre en place de manière efficace ces méthodes.
Objectif de la thèse
L'objectif de la thèse est de proposer des méthodologies permettant de modéliser et de résoudre des problèmes pratiques de découpe à l'aide de modèles mathématiques. Le principal défi est le passage à l'échelle sur des données de grande taille, ainsi que la prise en compte de contraintes non standard (formes complexes à découper, contraintes pratiques sur la découpe, etc.).
Pour répondre à ce défi, il s'agira d'étendre les résultats actuels permettant la génération différée de contraintes et de variables, d'agrégation de modèles, et de reformulation de programmes linéaires en nombres entiers.
Le doctorant sera aussi amené à étudier des techniques permettant d'hybrider la programmation mathématique avec d'autre paradigmes d'optimisation (programmation dynamique, programmation par contraintes, heuristiques).
Les algorithmes seront implantés à l'aide de la bibliothèque logicielle BaPCod développée par l'équipe realopt.
Compétences attendues pour le candidat
Le candidat devra posséder de bonnes bases en programmation linéaire, et en programmation orientée objet. La mise en place lors de projets/stages d'approches de génération de colonnes serait un plus certain. Une connaissance préalable du langage C++ serait aussi très appréciée.