Séminaires de l'équipe GROG

 

• Jeudi 10 décembre 2015 à 14h00, G-SCOP, salle C319 : Sourour Elloumi (ENSIIE), Linéarisation et reformulation quadratique convexe pour l'optimisation quadratique.

  - A. Billionnet et S. Elloumi. Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem . Mathematical Programming, 109(1): 55-68, 2007
- A. Billionnet, S. Elloumi et M.-C. Plateau. Improving standard solvers convex reformulation for constrained quadratic 0-1 programs: the QCR method. Discrete Applied Math, vol. 157(6), 2009, pp. 1185-1197.- A. Billionnet, S. Elloumi et A. Lambert. Extending the QCR method to general mixed-integer programs. Mathematical Programming, vol. 131(1), 2012, pp.381-401
 

• Jeudi 12 novembre 2015 à 14h30, G-SCOP, C319 : Hélène Soubaras (THALES), Méthodes locales pour la réparation en ordonnancement de FJSP avec déplacements.

Le recours aux techniques de réparation de plan est nécessaire lorsque, durant l'exécution du plan, une perturbation vient le rendre invalide ou sous-optimal. On s'intéresse ici à la réparation des séquences en ordonnancement du problème FJSP (Flexible Job-Shop Problem, ou problème d'atelier flexible).

Comme nous l'avons montré dans une précédente publication (MCO 2015), les méthodes de résolution par recherche locale s'appliquent bien à l'adaptation et la réparation car elles favorisent un critère supplémentaire, qui est de limiter le nombre de changements par rapport au plan initial - ceci peut être souhaité pour des raisons opérationnelles. Nous avons proposé en particulier l'algorithme du taquin à potentiel (ou 15-puzzle algorithm), qui est une variante plus rapide de la recherche tabou.

Nous proposons d'étendre ces méthodes à des problèmes de FJSP avec déplacements, qui sont des FJSP avec transport simplifiés (il n'y a pas de problème des ressources de transport à gérer). Nous montrerons une application à la planification de mission de drones en essaim, lorsqu'un drone tombe en panne.
 

• Jeudi 22 octobre 2015 à 12h, G-SCOP, C319 : Hugo Joudrier (G-SCOP), Guaranteed Global Deterministic Optimization and Constraint Programming for Complex Dynamic Design Problem.

- Algebraic constraints : used to describe the components from a static point of view (size, weight, density, volume, stiffness...). They usually stem from the engineering and are non-convex, sometimes non continuous.
- Functional constraints : are used to describe some physico-chemical properties (electric, mecanic, electromagnetic, thermal, kinetics...), wear or any modelable features evolving with the component use. They are usually described by some ordinary differential equations.

1. Interval Arithmetic
2. Tube Arithmetic
3. Guaranteed Integration Schemes
4. Constraint Programming
5. Interval Branch and Bound

• Jeudi 11 juin 2015 à 12h, G-SCOP, salle C319 : Alain Nguyen (Renault), Outils d’optimisation dans la chaîne logistique de RENAULT.
  À la suite, Olivier Briant (G-SCOP) à 14h40 nous présentera algorithme vainqueur du Challenge ESICUP 2015 sur le remplissage 3D des conteneurs de Renault.

RENAULT a recours aux algorithmes de recherche opérationnelle pour traiter différentes problématiques d’optimisation dans sa chaîne logistique, tant au niveau opérationnel qu’au niveaux tactique et stratégique. Ces outils d’optimisation sont présents à la fois en logistique amont (flux des fournisseurs vers les usines) qu’en logistique aval (flux des usines vers les concessions). Ils servent également aux échanges entre la direction commerciale (qui exprime des demandes de fabrications) et la direction logistique (qui construit une réponse industrielle).

 

• Jeudi 28 mai 2015 à 12h, G-SCOP, salle C319 : Sylvain Ducomman (G-SCOP / Geoconcept) Approche modulaire pour la résolution de problème de tournées de véhicules de grandes tailles.

Sous l'effet de l'industrialisation et de la mondialisation, la logistique et le transport sont désormais des éléments essentiels de l'économie moderne. En 2011, la branche transport et entreposage représentait 9,7% de la valeur ajoutée brute totale (source INSEE).
GEOCONCEPT-SA. propose des solutions pour l'optimisation des problèmes de tournées de véhicules. Ces problèmes ont pour but de répartir, entre des véhicules, un ensemble de visites et des les ordonner au sein de chaque tournée.

Les applications peuvent être diverses. En effet, cela peut aussi bien concerner les tournées de livraison, les tournées de collecte de marchandises ou de personnes, que la planification des visites médicales à domicile. Cependant, cette diversité d'applications engendre des contraintes diverses et variées qui ne peuvent pas toutes être retrouvées dans la littérature.

Afin de modéliser les problèmes d'un large éventail de clients, GEOCONCEPT-SA développe un nouveau moteur de calcul pour les tournées de véhicules permettant d'élargir la gamme des problèmes résolus. La réalisation de ma thèse s'inscrit dans le développement de ce nouveau moteur de calcul afin d'apporter une base solide et modulaire basée sur la Programmation par Contrainte.

Dans la première partie de l’exposé, nous verrons l’approche proposée pour le nouveau moteur de calcul. Dans la seconde partie, nous étudierons la résolution d’un problème de base de tournées de véhicule, celui du problème du voyageur de commerce avec fenêtres de temps. Cette résolution s’appuie sur une contrainte globale que nous améliorons par des mécanismes de filtrage basés sur les coûts.

 

• Jeudi 21 mai 2015 à 14h30, G-SCOP, salle C319 : Nicolas Zufferey (Université de Genève) Diversion opportunities in vehicle routing with variable travel times and online positioning.

This talk analyzes the impact of vehicle tracking devices, such as global positioning systems, on a vehicle routing problem with time windows in the presence of dynamic customer requests and dynamic travel times. It is empirically demonstrated that substantial improvements are achieved over a previously reported model which does not assume such tracking devices. We also analyze how the system handles dynamic perturbations to the travel times that lead to earliness or lateness in the planned schedule. This is a joint work with Jean Respen (GSEM – University of Geneva) and Jean-Yves Potvin (CIRRELT – University of Montreal).
 

• Jeudi 30 avril 2015 à 12h, G-SCOP, salle C319 : Emna Mhiri (G-SCOP), Prise en compte des priorités des lots et de la capacité des ressources pour la projection des encours de production dans l’industrie des semi-conducteurs

L’industrie des semi-conducteurs est caractérisée par une production de forte variabilité et faible volume, des flux de production réentrants et un processus de fabrication assez complexe composé de plus que 200 opérations et 1100 tâches élémentaires. Ces tâches sont exécutées sur des machines ayant différents modes opératoires (une seule plaque, lot ou batch, série ou parallèle...). La planification de la capacité au sein de cet environnement semble très difficile et assez importante.
Pour cette thématique, l’analyse des écarts entre la littérature et les observations réalisées sur le terrain permet de dégager deux axes de recherche : la prise en compte des priorités des lots (les dates d’échéance de livraison) d’une part, et de la capacité des ressources d’autre part.

Dans cette optique, nous avons modélisé le problème de planification de la production à capacité finie considérant les contraintes de cet environnement industriel sous forme d’un programme linéaire mixte (MIP) dont l’objectif est la minimisation des retards de livraison.
Vu que l'approche proposée est appliquée à une étude de cas réelle, celle de STMicroelectronics Crolles, la méthode exacte présente des limites de résolution en termes de temps d’exécution et mémoire informatique vu la taille des données réelles testées. Ainsi, une méthode approchée est proposée. Il s’agit d’un algorithme itératif par périodes de l'horizon de planification.
Cet algorithme est composé de trois modules :
- Un module de projection des encours de production à capacité infinie permettant de calculer un coefficient de temps de cycle par lot tenant compte de sa due date et permettant aussi l'estimation des dates de début et de fin de chaque tâche de fabrication restante;
-Un module de calcul de la charge cumulée sur les équipements tout en équilibrant la charge entre les équipements ayant les mêmes qualifications et partageant les mêmes recettes;
-Un module d'équilibrage de la charge et la capacité en cas de surcharge tout en reportant l'exécution des tâches engendrant la surcharge à des périodes ultérieures de l'horizon.

Les résultats obtenus en utilisant des données réelles montrent la performance de l'heuristique proposée par rapport aux techniques employées en termes de planification des capacités et temps de calcul.

 

• Jeudi 2 avril 2015 à 14h30, G-SCOP, salle C219 : David Monniaux (VERIMAG) Worst-case execution time as a combinatorial optimization problem

Bounds on the worst-case execution time of reactive control software, taking into account cache and pipeline effects, can be improved by taking into account infeasible paths. We express the problem as maximization within the solution set of a satisfiability modulo theory (SMT) problem. Unfortunately this generates formulas of a hard class for all solvers based on the DPLL(T) scheme (all production-grade solvers). We thus introduced cuts that make tractable previously intractable problems.

(papier avec Julien Henry et Claire Maiza et Mihail Asavoae publié à LCTES 2014)
 

• Jeudi 26 mars 2015 à 12h, G-SCOP, salle C319 : Matthieu Guillot (G-SCOP), Plus courts chemins stochastiques appliqués au jeu de golf.

Un joueur de golf cherche à minimiser le nombre de coups pour rentrer sa balle dans le trou. Pour cela, il doit décider à chaque coup, dans quelle direction jouer et quelle distance parcourir, c.à.d. déterminer un point cible intermédiaire entre le départ et le trou, et itérer depuis sa nouvelle position jusqu’à ce que sa balle rentre. Lorsqu’un joueur sait parfaitement viser une cible donnée, le problème se ramène à un problème de plus court chemin : il faut essentiellement déterminer où placer les cibles intermédiaires de manière à éviter les obstacles (eau, arbres, sable, etc…). Cependant, en général, les trajectoires effectives diffèrent plus ou moins des trajectoires souhaitées en fonction du degré d’habilité du joueur. Le problème devient alors stochastique et le joueur doit maintenant déterminer une stratégie : quel coup jouer à partir de n’importe quelle position possible sur le terrain (puisqu’il ne sait plus à l’avance là où il risque d’atterrir). On se propose d’étudier le problème où le joueur cherche à minimiser le nombre de coups moyen : ce problème se ramène à un problème de plus court chemin stochastique.  Nous présenterons ici les hypothèses utilisées pour modéliser notre problème : représentation du terrain, modélisation des joueurs, trajectoires de balle, etc… ainsi que l’outil de simulation que nous avons développé pour évaluer le résultat d’un coup et/ou d’une stratégie donnés. Nous détaillerons également la première stratégie gloutonne que nous avons mise en œuvre, utile à la fois comme test de notre simulateur, et comme solution initiale de nos futurs algorithmes d’optimisation. Nous expliquerons ensuite comment utiliser notre simulateur pour instancier le problème de plus court chemin stochastique (états, actions et matrice de transition) et les outils que nous utiliseront pour résoudre ce problème.
 

• Jeudi 19 mars 2015 à 14h30, G-SCOP, salle C319 : Sofia Zaourar (XEROX) Optimisation convexe non-différentiable et méthodes de décomposition en recherche opérationnelle.

Nous nous intéressons à la résolution de problèmes d'optimisation de grande taille, potentiellement non-linéaires et à variables mixtes; tels les problèmes classiques de conception de réseaux, le problème de planification de production électrique d'EDF, ou encore le problème de réaffectation de machines de Google. Ces problèmes, hors de portée des méthodes de résolution frontales, ont une structure décomposable qui peut être exploitée. Cependant, leur résolution par les approches de décomposition classiques présente encore de nombreux défis. Dans cette thèse, nous adoptons un point de vue d'optimisation convexe non-différentiable sur les méthodes de décomposition pour en proposer de nouvelles variantes adaptées à ces problèmes difficiles. Plus précisément, nous présentons : (1) une accélération de la décomposition de Benders utilisant une stabilisation algorithmique; (2) une régularisation de la décomposition lagrangienne dans le but d'améliorer la structure des solutions; (3) un moyen de tirer parti d'informations faciles à obtenir mais de précision incontrôlée dans les algorithmes d'optimisation non-différentiable (souvent au cœur des approches de décomposition); (4) et enfin une nouvelle stratégie de décomposition pour le problème de réaffectation de machines, ainsi que des heuristiques efficaces pour la résolution des sous-problèmes engendrés.
 

• Jeudi 29 janvier 2015 à 12h, G-SCOP, salle C319 : Nicolas Brulard (G-SCOP / Jardins de Gally) Conception de fermes urbaines : un problème de dimensionnement et d’affectation de ressource

Dans un contexte d’urbanisation croissante et de raréfaction des terres arables, l’agriculture urbaine concentre de nombreux espoirs pour les villes de demain, tant pour la production locale de produits frais que pour les services rendus à la ville (pédagogie, valorisation des déchets organiques, …). Mais de nombreuses contraintes compliquent l’installation d’agriculteurs professionnels en ville : foncier contraint, logistique complexe, limitation des techniques autorisées. Nous cherchons donc à identifier et optimiser les critères et les contraintes de localisation et de dimensionnement de nouvelles formes de systèmes de production agricoles, incluant biens et services, en zone urbaine.

Les travaux que nous présentons concernent la première phase du programme : l’optimisation de la planification de la production. Il s’agit de déterminer quelles techniques de productions utiliser pour répondre à une demande en produits périssables, en utilisant au mieux la surface et la main d’œuvre disponible.
Travail réalisé en collaboration avec V. D. Cung et N. Catusse.
 

• Jeudi 19 décembre 2014 à 12h, G-SCOP, salle C319 : Widad Naji (G-SCOP) Incertitudes dans les problèmes d’optimisation : Modèles et Approches.

La prise en compte des incertitudes est un axe de recherche en plein essor en recherche opérationnelle et en aide à la décision. L'incertitude est une connaissance imparfaite des données qui affecte toutes les décisions relatives à des systèmes dont les données ou le comportement ne sont pas connus avec précision à l’avance. Sur la base de cette observation, les décideurs doivent résoudre des problèmes complexes dans des conditions de connaissance limitée des données et des informations. Cependant, si on procède à l’optimisation sans tenir compte de l'incertitude, la solution optimale du modèle risque souvent de dévier de l’optimum ou de devenir inapplicable au problème réel.
La prise en compte des incertitudes dans les modèles d’optimisation est donc un véritable verrou scientifique. De nombreux modèles d’incertitudes, formels ou pratiques, se sont développés ces dernières années. Parallèlement, de nombreuses approches d’optimisation ont connu un fort essor, particulièrement en programmation stochastique et en programmation robuste.
Dans la prise de décision sous incertitudes de données, de nombreux critères peuvent participer au choix d'une approche adéquate, à savoir : le type d'incertitude, le degré d’incertitude, l’objectif de la décision, la tolérance vis-à-vis du risque, etc.
Le but de notre présentation est de fournir une classification des différents types d’incertitudes rencontrées en optimisation, présenter les modèles qui permettent de les traiter, et classer les approches d’optimisation sous incertitudes selon les critères cités ci-dessus.
Travail réalisé en collaboration avec V. D. Cung, M. L. Espinouse.
 

• Jeudi 13 novembre 2014 (G-SCOP, salle C319) : Julien Darlay (Innovation 24, Groupe Bouygues, Paris) : Outil de déploiement du réseau fixe de Bouygues Telecom

 

• Lundi 20 octobre 2014 à 14h30 (G-SCOP): Alessandro Agnetis (Rome, Italie) : Coordination of production and interstage batch delivery with outsourced distribution

In this talk, we consider coordinated production and interstage batch delivery scheduling problems, where a third-party logistics provider (3PP) delivers semi-finished products in batches from one production location to another production location belonging to the same manufacturer. A batch cannot be delivered until all jobs of the batch are completed at the upstream stage. The 3PP is required to deliver each product within a time T from its release at the upstream stage. We consider two transportation modes: regular transportation, for which delivery departure times are fixed at the beginning, and express transportation, for which delivery departure times are flexible. We analyze the problems faced by the 3PP when either the manufacturer "dominates" (i.e., decides a certain production sequence and the 3PP must comply with it) or when the release sequence is negotiated between the two parties. In this context, we investigate the complexity of several problems, providing polynomiality and NP-completeness results.

[joint work with Mohamed Ali Aloulou (LAMSADE, Université Paris Dauphine), Liangliang Fu (LAMSADE, Université Paris Dauphine) and Mikhail Kovalyov (United Institute of Informatics Problems, National Academy of Sciences of Belarus, Minsk)]

• Jeudi 9 octobre 2014 à 14h30 (G-SCOP): Ariel Waserhole : SunHydrO : Stockage optimisé pour l'intégration d'énergie renouvelable

De nombreux pays comme la France se sont engagés à développer leur parc de production d’énergies renouvelables. La maturité croissante de ces infrastructures ouvre la voie vers de nouveaux modèles de financement, hors des tarifs d’achat garantis. Parallèlement, des évolutions réglementaires et l’émergence de nouveaux marchés (capacité, services systèmes) offre un cadre favorable au développement de nouvelles solutions de flexibilité.

Le projet SunHydro, porté par Sun'R Smart Energy, vise à développer un nouvel agrégateur EnR qui, en s'appuyant sur des moyens de flexibilité, tels que le stockage gravitaire décentralisé, valorisera directement sur les marchés de l’électricité des EnRs décentralisées.

Dans cette présentation, nous cherchons à optimiser la stratégie d'achat et de vente sur les marchés de l'énergie d'une centrale virtuelle composée d'une unité de stockage contrôlable et d'un parc de centrales EnR intermittentes.
Nous détaillerons les hypothèses prises pour formuler le problème dans un cadre d'optimisation stochastique.
Nous présenterons une approche de résolution par programmation stochastique.
Pour finir nous utiliserons des simulations de nos stratégies optimisées pour évaluer l'impact d'évolutions réglementaires des marchés de l'électricité.