GSCOP-RUB-GROG-poster

Séminaires de l'équipe GROG

Dates des prochains séminaires :

  • Les dates des pchains séminaires sont disponibles sur le calendrier suivant: ici


Archive des séminaires :


 

Résumés :

  • Jeudi 24 mars 2016 à 14h, G-SCOP, salle C319 : Sylvain Bouveret (LIG), Des critères d'équité pour le partage de biens indivisibles.
Le problème d'avoir à partager de manière efficace et équitable un ensemble d'objets indivisibles entre des agents est un problème complexe et ayant de nombreuses applications concrètes, allant de l'allocation de cours à des étudiants à l'allocation de tâches sur des machines. Dans cet exposé, après une introduction générale sur le problème de partage équitable de ressources, nous nous focaliserons sur le problème de partage sous hypothèse de préférences additives. Nous introduirons cinq critères formant une échelle linéaire permettant d'évaluer le degré d'équité d'un partage. Nous verrons que malgré leur simplicité, ces critères ont des propriétés extrêmement intéressantes et posent des problèmes de calcul (encore ouverts) épineux.
 
  • Mardi 9 février 2016 à 14h, G-SCOP, salle C219 : Michele Garraffa (Politecnico di Torino), Solving the Max-Mean Dispersion Problem to Optimality.

This work proposes an exact algorithm for the Max-Mean Dispersion Problem (Max-Mean DP), an NP-hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. The proposed approach embeds the SDP relaxation with a cutting plane algorithm into a branch and bound framework to solve Max-Mean DP instances to optimality. To authors' knowledge, this is the first exact algorithm that has been proposed for this problem. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up 100 elements, while standard methods for fractional combinatorial optimization manage instances whose size is less then or equal to 75. The presented approach can be generalized to other combinatorial problems with a quadratic fractional objective and linear constraints.
  • Jeudi 14 janvier 2016 à 12h30, G-SCOP, salle C319 : Michaël Gabay (Artelys), Optimisation dans les grands systèmes électriques.
La conception et la gestion des systèmes de production et de transport
d'électricité est un vaste domaine aux enjeux économiques et sociétaux majeurs.
Artelys répond à ces enjeux en fournissant des prestations d'analyse
quantitative et solutions d'optimisation clés en main.
 
Lors de cette présentation, seront présentées quelques-unes des facettes de
l'activité d'Artelys dans le domaine de l'énergie. Trois sujets illustrant
différentes problématiques de nos clients et partenaires seront présentés :
- Analyse des disparités régionales de coûts de transport de l'électricité en France [1]
- Utilisation des techniques d'optimisation (Optimal Power Flow) pour calculer
     un état réaliste du réseau de transport Européen avec des données hétérogènes [2,3].
- Présentation de l'outil Artelys Crystal Super Grid. Logiciel de modélisation,
     simulation et optimisation de la production et du transport d'énergie. Artelys
     Crystal Super Grid permet de réaliser aisément et efficacement l'analyse
     coûts/bénéfices des systèmes de production et transport d'énergie et
     l'optimisation (flux, productions, capacités) de ceux-ci.
 
[1] Consultation publique de la CRE du 22 juillet 2015 relative à la structure
des tarifs d’utilisation des réseaux publics d’électricité, Annexe 3 : Etude
sur la tarification des injections dans les réseaux de transport électriques,
Analyse quantitative : Simulation, calcul et analyse des fondamentaux d’une
tarification zonale, http://www.cre.fr/documents/consultations-publiques/structure-des-tarifs-d-utilisation-des-reseaux-publics-d-electricite/
 
[2] Ruiz M., Maeght J., Marié A., Panciatici P., & Renaud A. (2014, August).
A progressive method to solve large-scale AC Optimal Power Flow with discrete
variables and control of the feasibility. In Power Systems Computation
Conference (PSCC), 2014 (pp. 1-7). IEEE.
 
[3] Ruiz M., Gabay M., Maeght J., Lefevre M., & Panciatici P. (2015, June).
Optimization based method to consolidate European Transmission Data. In
PowerTech, 2015 IEEE Eindhoven (pp. 1-6). IEEE.

 
  • Jeudi 10 décembre 2015 à 14h00, G-SCOP, salle C319 : Sourour Elloumi (ENSIIE), Linéarisation et reformulation quadratique convexe pour l'optimisation quadratique.
 
Nous considérons le problème (QP) de la minimisation d’une fonction quadratique sous des contraintes linéaires ou quadratiques. Les variables sont entières ou réelles, et bornées. Ce problème très général permet de modéliser de nombreux problèmes classiques en Optimisation Combinatoire et constitue une première généralisation de la programmation linéaire en nombres entiers.

Une différence majeure entre (QP) et les programmes linéaires en nombres entiers réside dans le fait que, en général, sa relaxation continue fournit un problème lui aussi NP-difficile. Pour contourner cette difficulté, la reformulation quadratique convexe transforme (QP) en un problème (QP') équivalent mais dont la relaxation continue est un problème convexe. Afin de calculer une solution optimale de (QP), on peut alors résoudre (QP') par un algorithme d'énumération implicite basé sur l'optimisation continue convexe.

Nous faisons un tour d'horizon de développements récents de cette approche. Nous montrons en particulier comment les relaxations semi-définies positives permettent de construire les problèmes équivalents (QP') les plus intéressants. Dans le cas des variables binaires, nous donnons une vision des linéarisations classiques comme un cas particulier de reformulation quadratique convexe.

Enfin, nous illustrons la généralité et l’efficacité expérimentale de la résolution exacte par reformulation quadratique convexe sur différents problèmes d’Optimisation Combinatoire.

Références :
 
- 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.
In this talk, I present my work about guaranteed methods to solve some multi-physics (mechanic, magnetic, electronic...) dynamic design problems. The engineering science needs to get some tools to help the decision making during the development stages.

These problems contain two type of constraints :
 
- 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.
Piecewise ordinary differential equations : in addition to this complexity, I also consider these particular differential constraints wich are useful to model some dynamic behaviors with some changing phases depending from the state of the components.

The multi-objective optimization is motivated by handling some conflicting objectives because design problems oftenly involves multiple criteria such as investment, profit, quality, efficiency, operation time...

The guaranteed global deterministic method used to solve these optimization problems is based on :
  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
Innovation 24 est la société du groupe Bouygues prenant en charge les sujets de recherche opérationnelle des différents métiers (Bouygues Construction, Telecom, Immobilier ainsi que TF1 et Colas). Dans cette présentation, nous verrons un outil développé pour aider Bouygues Telecom a étendre son réseau fixe. Il s’agit de sélectionner les nœuds de raccordement abonnés à dégrouper parmi l’ensemble des nœuds couvrant la France en maximisant le revenu de l’opération (gain d’abonnés moins coûts de déploiement). Ce problème se modélise comme un problème d’optimisation dans les graphes. Il s’agit d’une variante du problème de prize collecting steiner tree avec des contraintes additionnelles sur la structure des solutions. Nous verrons la modélisation du problème, sa résolution avec une heuristique de recherche locale et le calcul du borne supérieure permettant d’évaluer les solutions.
 
  • 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é.