Tutoriels 2017 du GDR RO

Le GDR RO organise le 23 février 2017
- son AG de 13h50 à 14h05
- des tutoriels de 14h05 à 15h45
pendant la conférence ROADEF 2017 à Metz
Voir le site des tutoriels : http://roadef2017.event.univ-lorraine.fr/speakers.html
Voir le programme officiel: http://roadef2017.event.univ-lorraine.fr/program_planning.html

Liste de ces tutoriels

Algorithmes approchés: une frontière sur les compromis temps/qualité

Bruno Escoffier UPMC, LIP6, Paris

La conception d'algorithmes approchés pour la résolution de problèmes difficiles montre l'existence de compromis algorithmiques possibles entre qualité de la solution calculée et complexité en temps. En grande partie focalisée sur les algorithmes de complexité polynomiale, un des développements récents de la thématique de l'approximation concerne les compromis atteignables par des algorithmes de complexité plus élevée.
Nous retracerons dans cet exposé certaines avancées importantes de la théorie de l'approximation polynomiale, puis présenterons certains résultats plus récents concernant des complexités non polynomiales.

Optimisation Combinatoire: résolution par approches polyédrales et algorithmes de coupes

Pierre Fouilhoux UPMC, LIP6, Paris

Ce tutoriel présente les notions de base de l'approches polyédrales pour la résolution de problèmes d'optimisation combinatoire; ainsi que la mise en oeuvre des méthodes algorithmiques de coupes (Branch-and-Cut), en se basant sur des formulations linéaires comportant un nombre exponentiel d'inégalités.

Problème de règlement-livraison de nuit

Dan Gugenheim Banque de France, Paris

Le règlement-livraison titre consiste à effectuer un transfert de titres (action,obligation,…) entre deux acteurs, en échange d’un paiement en devise. En 2005, le rapport Giovannini met en évidence le manque d’efficacité du règlement livraison titre transfrontalier en Europe. De ce constat est né le projet Target2Securities (T2S), une nouvelle plate-forme de règlement-livraison dont le but est d’uniformiser les règles du marché européen et le rendre plus attractif.
Chaque journée de T2S est divisée en deux parties. Dans la première partie, dite période de nuit, les transactions sont réglées par lots et le but est de régler le plus possible de transactions. Dans la deuxième partie, dite période de jour, les transactions sont réglées en temps réel et une par une. La majorité des transactions sont réglées lors de la période de nuit.
La Banque de France est en charge du moteur de règlement de T2S. Une équipe dédiée, le LAB, a été créée afin de développer le Module d’Optimisation Mathématique de T2S. Son but est de régler le plus possible de transactions lors de la période de nuit à l’aide des techniques de recherche opérationnelle.
Plusieurs difficultés se sont présentées. Le temps d’exécution du Module d’Optimisation Mathématique est limité dû à des contraintes du marché. Le volume de données est très important et est amené à augmenter. Les montants et les quantités échangés sont importants et requièrent une grande précision numérique.
Depuis le lancement de T2S en juin 2015, le Module d’Optimisation Mathématique est opérationnel et répond aux besoins du marché. Cet exposé consiste en une présentation générale des travaux de la Banque de France. Après avoir donné quelques notions de finance, nous décrivons le problème de règlement-livraison. Puis nous exposons et illustrons les principales contraintes de notre modèle mathématique, avant de présenter les difficultés techniques rencontrées. Nous donnons ensuite une description générale des méthodes d’optimisation essayées et les résultats obtenus en production.

Robust combinatorial optimization

Michael Poss CNRS, LIRMM, Montpellier

Robust optimization (RO) has become a central framework to handle the uncertainty that arises in the parameters of optimization problems. While classical RO results can efficiently handle linear programs for a large variety of uncertainty sets, the situation is more complex for optimization problems involving discrete decisions. Efficient exact or approximate solution algorithms for such problems must exploit the combinatorial structure of the problems at hand. In this tutorial, we shall review key results of this field, which has witnessed a revival in the last ten years since the introduction of structured uncertainty sets (budget, ellipsoids, ...). We will show how the static robust counterparts of many polynomially solvable problems remain polynomially solvable, and highlight problems that turn NP-hard. We shall also review shortly the very recent propositions to address multi-stage counterparts where some discrete optimization variables can be adapted to the values taken by the uncertain parameters.

Problèmes de tournées sélectives

Aziz Moukrim Laboratoire Heudiasyc, UMR CNRS Université de Technologie de Compiègne

Les problèmes de tournées de véhicules font depuis quelques années l’objet de recherches intensives car ils apparaissent dans de nombreux domaines avec des objectifs intégrant des exigences associant performance, qualité de service, conditions de travail et respect de l’environnement.
Les problèmes de tournées sélectives est une famille de problèmes de tournées de véhicules (VRP) où a priori il n’est pas possible de servir tous les clients à cause de certaines contraintes de limitation de ressources. Dans sa version de base, on considère une flotte de véhicules avec un dépôt associé et un ensemble de n clients potentiels. A chaque client est associé un profit pouvant être collecté par un seul véhicule de la flotte, et à chaque arc du réseau on associe un temps de trajet. Le problème consiste à organiser les visites pour la flotte afin de maximiser la somme des profits collectés tout en respectant un temps de trajet limite imposé pour chaque véhicule. Plusieurs variantes ont vu le jour étant donné la complexité des contextes industriels d’application en termes de contraintes et d’objectif.
Dans le cadre de cet exposé, nous nous intéressons à la fois aux développements académiques récents et aux applications industrielles. Nous ferons une synthèse sur les approches de résolution exactes et approchées dédiées avec un focus sur la classification des instances.

Visual Analytics in the Environmental Sciences

Benoît Otjacques Head of e-Science Unit ERIN Department Luxembourg Institute of Science and Technology (LIST)

The data deluge heavily advertised some years ago has become a fact notably in the environmental sciences and in the green business. Vast amounts of environmental data are collected by satellites, in-situ sensors, field observations or citizen scientists. Large datasets are also produced by complex simulation runs on clusters of servers or High-Performance Computers. These datasets may take various forms: huge tables of experimental results mixing numerical or categorical variables, dynamic biological networks, large text corpora linked to ontologies, or geo-located images and videos.
Scientists and engineers use these types of datasets to solve scientific or technological problems. However, several paths exist to go from raw data to the answer of a question. This speech will focus on one of them: the visual analytics paradigm. Basically, it can be defined as the combined use of data analytics methods, data visualisation techniques and advanced interaction in order to gain insight into complex data.
This keynote speech will illustrate the visual analytics approach with example applications developed in the e-Science Unit of LIST (Luxembourg Institute of Science and Technology) ranging from the “omics sciences” to renewable energy and hydrology.