Le 10/12/2013 par clautiaux :

Offre de stage de master 2 : Problèmes de découpe 2D avec défauts

Stage à réaliser à l'Institut de Bordeaux, en collaboration avec la société Saint-Gobain

Rémunération :  1300 euros brut / mois

Contexte industriel

Dans le cadre de la découpe du verre, la société Saint-Gobain est confrontée à des problèmes de défauts dans les plaques de matière première. Lorsque l'on découpe des plaques de verre pour en extraire des formes rectangulaires, il est nécessaire de ne pas positionner des pièces sur ces défauts. Cette particularité n'est pas gérée par les modèles standards d'optimisation de découpe. Il est nécessaire de proposer de nouvelles approches afin de résoudre le problème efficacement.

Contexte académique

Une approche standard pour résoudre les problèmes linéaires en nombres entiers est d'utiliser des techniques de décomposition. 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 du stage

L'objectif du stage est de modéliser le problème de découpe rectangulaire avec défauts à l'aide d'un programme linéaire en nombres entiers et de proposer des techniques de résolution permettant de le résoudre. Une résolution frontale du modèle PLNE ne permettra pas de résoudre des problèmes de grande taille. La piste à étudier durant le stage est celle des méthodes de décomposition (Dantzig et Wolfe en particulier). Le niveau de décomposition à mettre en œuvre, ainsi que les algorithmes efficaces de résolution des sous-problèmes issus de la décomposition seront à déterminer durant le stage.

Travail à effectuer

1) Modéliser le problème réel à l'aide de la PLNE
2) Comparer différentes méthodes de décomposition
3) Mise en place de premiers algorithmes pour résoudre les sous-problèmes

Les algorithmes seront implantés à l'aide de la bibliothèque logicielle bapcod développée par l'équipe realopt.

Compétences attendue 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 (mais pas une obligation). Une connaissance préalable du langage C++ serait aussi appréciée.

Suite possible

Le stage est susceptible de déboucher sur une thèse CIFRE.

Contact

francois.clautiaux@math.u-bordeaux1.fr
Francois.Sausset@saint-gobain.com