Liste de ces tutoriels
Du bon usage de l’apprentissage statistique en recherche opérationnelle
Axel PARMENTIER (ENPC)
Porté par la vague du big-data, le nombre de contributions à la frontière de la recherche opérationnelle (RO) et de l’apprentissage statistique n’a cessé de croître ces dernières années. Si l’apprentissage statistique s’appuie principalement sur l’optimisation continue, les algorithmes de la RO se sont révélés pertinents pour traiter certains problèmes d’apprentissage avec structure. Les méthodes de l’apprentissage statistique sont quant à elles fréquemment utilisées pour résoudre des problèmes historiquement traités par la recherche opérationnelle, le plus souvent sans succès, mais avec quelques réussites retentissantes.
L’objectif de ce tutoriel est de présenter différents outils de l’apprentissage statistique, certaines de leurs applications pertinentes en RO, ainsi que des pièges à éviter. Après une introduction succincte de ces outils, nous ferons un bref panorama des contributions récentes de l’apprentissage statistique sur des problèmes de RO, puis nous nous focaliserons sur deux axes de recherche prometteurs : s’appuyer sur l’apprentissage pour accélérer les algorithmes, et tirer parti des modèles graphiques probabilistes pour l’optimisation en présence d’aléa.
Ordonnancements cycliques pour la conception de systèmes embarqués
Alix MUNIER (LIP6)
La conception de systèmes embarqués de plus en plus complexes nécessite le développement de méthodes efficaces pour optimiser les ressources et l’énergie.
Les applications sont généralement constituées d’un ensemble de tâches communicantes qu’il faut exécuter en permanence avec un débit fixé ou à maximiser.
Les « Synchronous Data Flow Graph » (SDF en abrégé), introduits en 1987 par Lee et Messerschmitt constituent un formalisme commun à plusieurs communautés scientifiques pour modéliser les échanges de données entre des tâches communicantes. Le but de cet exposé est de présenter les SDF et leurs applications dans la conception de systèmes pour l’automobile et l’avionique.
Dans un premier temps, nous présenterons ce formalisme, ainsi qu’un ensemble de propriétés mathématiques sur les contraintes de précédences entre les exécutions successives des tâches. Puis, nous montrerons que les SDF permettent de modéliser les communications de différents systèmes industriels exprimés sous la forme de systèmes multi-périodiques Simulink ou de contraintes temps-réels classiques. Nous terminerons sur la présentation de plusieurs études de problèmes d’optimisation de ressources d’un SDF sur une architecture embarquée.
Recherche Opérationnelle et Aide à la Décision pour le Management d’Energie, un panorama du domaine et quelques études de cas à EDF
Marc PORCHERON (EDF)
Le Management d’Energie désigne la gestion de l’ensemble des opérations mises en œuvre dans le processus de production, de transport, et de distribution d’énergie, jusqu’aux consommateurs finaux. Ce domaine, fondamental d’un point de vue technico-économique mais aussi environnemental et sociétal, a connu des bouleversements majeurs ces dernières années : développement des échanges sur les marchés de l’énergie, décentralisation grandissante de la production, déploiement des “smart grids”, part croissante des énergies renouvelables (ENR) dans le mix énergétique — avec les problèmes spécifiques liés à leur intermittence et les besoins en stockage associés,…
La résolution de très grands problèmes d’optimisation — souvent de nature stochastique compte tenu de l’incertitude qui pèsent sur leurs données (production des ENR, consommation, prix, disponibilité des moyens de production) — est au cœur de ce domaine. Comme exemple classique de ces problèmes on peut citer le unit-commitment qui consiste à décider quelles unités de production doivent être arrêtées/démarrées sur un horizon de temps donné, afin de satisfaire la demande en électricité à un moindre coût, tout en respectant les contraintes opérationnelles pesant sur le fonctionnement de ces unités et sur le réseau électrique.
Un grand nombre de ces problèmes sont de nature discrète/combinatoire et peuvent être modélisés comme des instances de problèmes NP-Complets classiques, ou, de façon générale, comme des problèmes linéaires en variables entières ou mixtes (PLNE, MIP).
Les techniques issues de l’optimisation discrète/combinatoire, qu’elles appartiennent au champ des méthodes « exactes » (Branch & Bound et ses variantes, reformulation, décomposition, génération de colonnes/coupes) ou à celui des méta-heuristiques (recherche locale, algorithmes génétiques, recuit simulé …) sont donc très largement utilisées pour attaquer ces problèmes.
Au-delà du problème de unit-commitment cité plus haut, les applications suivantes constituent quelques exemples de problèmes d’optimisation difficiles sur lesquels ces techniques sont utilisées à EDF : planification des arrêts pour rechargement et maintenance des centrales nucléaires, planification des opérations de maintenance et optimisation des opérations de rechargement du cœur effectuées durant ces arrêts, logistique des centres d’appel, planification des tournées des véhicules d’intervention sur le réseau de distribution, optimisation des recharges et des flexibilités des véhicules électriques…
Après un panorama du domaine nous présenterons quelques-unes des techniques mises en œuvre au Département OSIRIS de la R&D d’EDF pour traiter ces problèmes et développer des outils d’aide à la décision à destination des équipes opérationnelles, en les illustrant sur des exemples concrets.
Optimization in Graphical Models
Georges KATSIRELOS (INRA TOULOUSE)
I will present Graphical Models as a framework for optimization and probabilistic reasoning. In this context, I will present two closely related solution methods, Weighted Constraint Satisfaction Problems and Maximum Satisfiability, and show how they exploit connections to logical formalisms and to techniques from linear programming.
Une introduction à la Complexité Paramétrée
Bruno ESCOFFIER (LIP6)
Etudiée depuis les années 90, la complexité paramétrée a connu depuis une bonne dizaine d’années un essor considérable et c’est à présent une approche très classique pour la résolution de problèmes d’optimisation combinatoire. Noyaux, algorithmes FPT, W[1]-difficulté (et d’autres choses encore) seront au menu de ce tutoriel dont l’objectif est de présenter les notions principales du domaine et de les illustrer par quelques exemples classiques.
Applications of operations in urban mobility with a special focus on electric vehicles
Jakob PUCHINGER (EC Paris, SystemX)
The worldwide proportion of people living in urban areas is expected to rise in the coming decades, reaching 67% by 2050. This growth gives rise to multiple challenges in urban mobility regarding passenger and goods transport while considering local and global pollutant emissions. This tutorial will start by posing major current and future challenges in urban mobility. We will then explore basic applications of operations research methods for urban mobility starting from shortest/fastest path calculations, over to the traveling salesman and vehicle routing problems. We will explore recent developments with regards to methods taking into account dynamic travel times and energy consumption. Finally we will present recent research results on electric vehicle routing problem variants. We will give some detailed descriptions of models and modelling challenges with regards to the consideration of energy consumption and recharging. We then present several different exact and heuristic solution approaches and case studies that have been proposed in the last years.