A. Ridha Mahjoub
LAMSADE, Université Paris-Dauphine, Paris, France
mahjoub@lamsade.dauphine.fr
For the past few decades, combinatorial optimization techniques have shown to be powerful tools for formulating, analysing and solving problems arising from practical decision situations. In particular, polyhedral approaches have been successfully applied for many well known NP-hard problems. The equivalence between separation and optimization over a polyhedron has been behind a great evolution of these methods. The so-called « Branch and Cut » method, which is inspired from this equivalence, is now widely used for obtaining optimal and near-optimal solutions for hard combinatorial optimization problems. In this talk we will discuss applications of these techniques to some network design problems. In particular we will consider the so-called survivable network design problem. This has many real world applications (e.g. telecommunication and transportation networks, VLSI networks). A big amount of research has then been done for designing algorithmic approaches for that model. Network survivability means the ability to restore service in the event of a catastrophic failure of a network component, such as the complete loss of a link or the failure of a node. Service could be restored by routing traffic through other existing links and nodes, assuming that the network could provide additional connectivity. Designing a network meeting requirements concerning traffic survivability is now a major challenge with great economic impact. Survivability requirements are generally formulated in terms of network connectivity. We will first discuss some variants of this model and the related polyhedra. In particular, we will describe some classes of valid inequalities, which have shown to play an important role, and discuss their separation aspect.
Then we will consider network design problems when the routing paths have to be bounded. Connectivity requirements may not unfortunately be sufficient to guarantee a high routing quality in the network. Indeed, the alternative routing paths may be too long and so costly to be suitable. In order to limit the rerouting length, it is commonly required that the length of the paths between the origin-destinations is bounded by a given constant depending on technological parameters. So if a failure occurs, then the traffic can be rerouted through a bounded path. Integer programming formulations as well as cutting plane based algorithms will be discussed.
Finally some extensions related to dimensioning problems, when adequate capacities have to be installed in the network, will be considered.
BIO-SKETCH
A. Ridha Mahjoub is Classe Exceptionnelle Professor of Operations Research and Combinatorial Optimization at Université Paris-Dauphine, Paris, France. He is also member of the LAMSADE laboratory, CNRS. Previous positions include full professor at the University of Brest, France, from 1991 to 1998 and the University of Clermont-Ferrand, France, from 1998 to 2007. Professor Mahjoub holds an undergraduate degree in Mathematics from University of Tunis, Tunisia and a Ph.D. and a Thèse d’Etat in Operations Research and Combinatorial Optimization from the University of Grenoble, France. His research areas include the theory and applications of polyhedral approaches for modeling, analysing and solving large NP-hard combinatorial optimization problems, mixed integer programming as well as complexity and graph theory. A part of his research has recently focused on the design of cutting plane algorithms for network design problems. Professor Mahjoub is author and co-author of several papers that have appeared in leading journals such as Mathematical Programming, Mathematics of Operations Research, SIAM Journal on Discrete Mathematics, Discrete Mathematics, Discrete Applied Mathematics, Discrete Optimization, Informs Journal on Computing, Operations Research letters and Networks. He served as co-director of the Mathematics and Computer Science Department at Université Paris-Dauphine between 2008 and 2013. Dr Mahjoub edited and co-edited books and several special issues of journals. He currently serves as Editor-in-Chief of the international journal RAIRO-Operations Research and Associate Editor of Computers and Industrial Engineering.
A general purpose technique for approximation algorithms
Dorit S. Hochbaum
Department of IE&OR
Etcheverry Hall,
University of California,
Berkeley Ca.
hochbaum@ieor.berkeley.edu
The class of integer programs where each constraint has up to two variables, IP2, is shown to have 2-approximation algorithms that are derived in polynomial time by solving a minimum cut problem on an associated graph. Prominent NP-hard problems that can be formulated as IP2 problems include: Vertex Cover, minimum satisfiability, min 2-SAT, the max clique represented as a min node deletion problem, several submodular minimization problem (also on multi-sets) and others.
Interesting applications in which the IP2 formulation has monotone constraints (the coefficients of the two variables have opposite signs) are solved in integers in polynomial time. Applications that have been discovered to be polynomial time solvable under this framework include data mining, image segmentation, certain Rayleigh ratio problems and other ratio problems all of which are polynomial time solvable with an extension of the techniques described.
The results extend to formulations with three variables per inequality where a third variable can appear in one constraint only. These problems have a polynomial time algorithm to generate super optimal half integral solution which, if they can be rounded to a feasible solution, generate 2-approximate solutions. If the constraints are monotone, then optimal solutions are found in polynomial time.
BIO-SKETCH
Dorit S. Hochbaum is a full professor and Chancellor chair at UC Berkeley's department of Industrial Engineering and Operations Research (IEOR). Her research interests are in the areas of design and analysis of computer algorithms, approximation algorithms and discrete and continuous optimization. Her recent work focuses on efficient techniques related to network flows with novel applications in ranking, pattern recognition, data mining and image segmentation problems.
Professor Hochbaum is the author of over 150 papers that appeared in the Operations Research, Management Science and Theoretical Computer Science literature. Prof. Dorit S. Hochbaum was awarded an honorary doctorate of sciences by the University of Copenhagen recognizing Hochbaum's ground-breaking achievements and leadership in optimization in general and in the field of approximation algorithms for intractable problems in particular. Hochbaum was awarded the title of INFORMS fellow for the extent of her contributions to Operations Research, Management Science and design of algorithms. She is the winner of the 2011 INFORMS Computing Society prize for best paper dealing with the Operations Research/Computer Science interface. Professor Hochbaum was named fellow of the Society of Industrial and Applied Mathematics (SIAM) in 2014.
Sparsification et approximation sous-exponentielle
Le concept de la « sparsification des instances » est un outil bien connu dans le paradigme du calcul exact étant donné que cette notion est très fortement liée à l’Hypothèse du Temps Exponentiel (Exponential Time Hypothesis). Dans cette présentation, nous décrivons quelques premiers pas qui tentent d’étendre la notion de sparsification dans le but d’en faire un outil pour l’approximation sous-exponentielle. Plus spécifiquement, nous décrivons un nouvel outil pour l’inapproximabilité sous-exponentielle, la « sparsification qui préserve l’approximabilité » et montrons comment on peut utiliser cet outil afin d’obtenir les résultats d’inapproximabilité exponentielle pour des problèmes fondamentaux d’optimisation combinatoire tels l’ensemble dominant minimum, la couverture minimum d’ensembles, etc.
BIO-SKETCH
Vangelis Paschos is Professor of Computer Science in the University
Paris-Dauphine and member of the reseach lab LAMSADE. He is currently working
on Complexity Theory, Efficient Approximation of Hard Problems and Combinatorial
Optimization. Professor Paschos published more then 100 articles in top international j
ournals. He is a member in the editorial board of
Theoretical Computer Science,
European Journal of Operational Research, RAIRO - Operations Research, among others.
He is senior member of the "Institut Universitaire de France".
Caractérisation de la flexibilité d'un consommateur d'énergie et optimisation de son usage : un problème multiforme
Claude Le Pape
Schneider Electric
La réduction des pics de consommation d'électricité (coûteux aussi bien financièrement qu'en émission de CO2) suppose que diverses organisations adaptent leurs activités pour réduire ou décaler dans le temps tout ou partie de leur consommation. Les incitations correspondantes sont multiples : économies de consommation par coordination d'actions génératrices et consommatrices d?énergie, tarifs variables dans le temps, compensations d'actions volontaires d'ajustement en temps quasi-réel de la consommation, etc. Ces incitations doivent cependant être considérées en regard des objectifs propres de l'organisation concernée (fabrication et livraison de produits en temps utile, services de qualité, pérennité des installations) et des facteurs de coût non-énergétiques.
En pratique, la flexibilité d'un consommateur d'énergie peut être de trois ordres: (i) la capacité d'établir un compromis entre la quantité d'énergie consommée et le service rendu, par exemple en réduisant temporairement la luminosité d'un système d'éclairage; (ii) la capacité d'anticiper ou de retarder des activités fortement consommatrices; (iii) la capacité de stocker temporairement de l'énergie, quitte à en perdre une partie. Considérées séparément, ces capacités induisent des modèles d'optimisation différents les uns des autres : régulation multi-critère; ordonnancement sous contraintes de ressources et coûts énergétiques; optimisation de flux et de stocks. Les choses se compliquent lorsque ces capacités s'ajoutent les unes aux autres et notamment lorsque l'on considère plusieurs acteurs qui partagent le même réseau d'énergie, tout en conservant chacun ses objectifs et ses contraintes propres ...
NOTA BENE
Les exemples qui illustreront le propos de cette présentation seront pour l'essentiel tirés des thèses de Chloé Desdouits (Réduction des pics de consommation d'électricité et problèmes d'optimisation induits pour les consommateurs, GIPSA-Lab, LIRMM & Schneider Electric) et Peter Pflaum (Stratégies de gestion d'énergie pour les smart grids, GIPSA-Lab & Schneider Electric).
Travaux financés en partie dans le cadre des projets Européens Arrowhead et Ambassador.
BIO-SKETCH
Claude Le Pape est chez Schneider Electric en charge de coordonner l'évaluation de nouvelles technologies et la reconnaissance des experts dans le domaine de l'optimisation et des méthodes analytiques. Titulaire d?un doctorat en Informatique de l'Université Paris XI et d'un MBA du Collège des Ingénieurs, il a été employé successivement en tant qu'étudiant post-doctorant à l'Université de Stanford, consultant et développeur de logiciels d'optimisation chez ILOG S.A. et Bouygues S.A., et directeur d'équipes de R&D chez Bouygues Telecom et ILOG S.A. Il a participé à plusieurs projets Européens et au développement de nombreux outils logiciels et applications industrielles dans des domaines variés : conception de mélanges de produits chimiques, gestion de stocks, planification d'évolutions de personnel sur le long terme, ordonnancement de chantiers de construction, planification industrielle et ordonnancement d'ateliers.
Shelter Location and Evacuation Traffic Assignment under Uncertainty
Hande Yaman
Bilkent University, Turquie
Shelters are safe facilities that protect a population from possible damaging effects of a disaster. The time to evacuate a region depends on the locations of shelters and the traffic on the routes. For this reason, shelter location and traffic assignment decisions should be considered simultaneously for an efficient evacuation plan. In addition, as it is very difficult to anticipate the exact place, time and scale of a disaster, one needs to take into account the uncertainty for a realistic evacuation plan. In this talk, we first present a scenario-based two-stage stochastic evacuation planning model that optimally locates shelters and that assigns evacuees to shelters and routes in an efficient and fair way to minimize the expected total evacuation time. We report the results of experiments on the impact of incorporating uncertainty into the problem and the trade-off between efficiency and fairness. Then we propose an exact algorithm based on Benders decomposition where the subproblem is a second order cone programming problem. We use duality results for second order cone programming in a Benders decomposition setting. We investigate techniques such as multi-cut strategy, pareto-optimal cuts, and preemptive priority multiobjective program to enhance the proposed algorithm. We also use a cutting plane algorithm in solving the dual subproblem to avoid memory problems for large instances. Computational results confirm the efficiency of our algorithms. This is joint work with Vedat Bayram. This research is supported by TUBITAK grant no. 213M434.
BIO-SKETCH
Hande Yaman received B.S. and M.S. degrees in Industrial Engineering from Bilkent University, and a Ph.D. degree in Operations Research from Universite Libre de Bruxelles. She joined the Department of Industrial Engineering at Bilkent University in 2003. She spent a year as a visiting researcher at CORE, Universite catholique de Louvain. Her research interests are in exact methods for mixed integer programming with applications in production planning, logistics, and network design.
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.
BIO-SKETCH
Bruno Escoffier a reçu son Doctorat en 2005 et son Habilitation à
Diriger des Recherches en 2012, tous deux en Informatique et de
l'Université Paris-Dauphine, établissement où il a été Maître de
Conférences entre 2006 et 2013. Depuis 2013 il est Professeur à l'UPMC
et membre de l'équipe "Recherche Opérationnelle" du laboratoire LIP6. Il
travaille sur la conception d'algorithmes approchés, exponentiels et
paramétrés pour la résolution de problèmes d'optimisation difficiles. Il
est l'auteur d'une trentaine d'articles dans des revues internationales,
et a reçu la médaille de bronze du CNRS en 2011.
Optimisation Combinatoire: résolution par approches polyédrales et algorithmes de coupes
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.
BIO-SKETCH
Pierre Fouilhoux a obtenu son doctorat en recherche opérationnelle au laboratoire LIMOS de l'Université Blaise Pascal à Clermont-Ferrand en 2004. Il a été nommé Maître de Conférences au laboratoire LIP6 de l'Université Pierre et Marie Curie à Paris en 2005. Ses centres d'intérêt sont l'optimisation combinatoire et la programmation mathématique (approches polyédrales, méthodes de décomposition...).
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.
BIO-SKETCH
Dan Gugenheim est diplômé de l’ENSIMAG en 2005. Après avoir travaillé deux ans au sein du département de recherche de l’Institut National de l’Audiovisuel, il suit à l’UPMC un Master 2 en recherche opérationnelle qu’il obtient en 2008. Il fait ensuite sa thèse sur l’optimisation et le dimensionnement des réseaux de transport de gaz à GDF SUEZ et soutient en 2011. En 2013 il intègre la Banque de France et devient le chef de l’équipe en charge du Module d’Optimisation Mathématique pour le règlement-livraison de nuit de Target 2 Securities, le plus gros projet de l’Eurosystème. Ses domaines d’intérêt sont l’optimisation combinatoire, l’optimisation non linéaire en nombres entiers et l’optimisation dans les réseaux. Il a obtenu également un CAP cuisine.
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.
BIO-SKETCH
Michael Poss a soutenu sa thèse à l'Université Libre de Bruxelles en 2011, suivie par un postdoctorat au Portugal (Aveiro et Coimbra). Il a rejoint le CNRS en 2012 pour travailler dans le laboratoire Heudiasyc, avant de muter au LIRMM en 2014 où il effectue actuellement ses recherches au sein de l'équipe MAORE. Ses travaux récents traitent essentiellement de l'optimisation robuste combinatoire, sujet de sa soutenance d'HdR en 2016, via la programmation mathématique en nombres entiers, et les algorithmes combinatoires. Il dirige plusieurs projets scientifiques (ANR, PHC-Pessoa, ...) et a publié différents articles sur le sujet (Oper. Res., Math. Prog., SIAM J. Opt.).
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.
BIO-SKETCH
Aziz MOUKRIM a obtenu une thèse d’université en informatique en 1995 à l’Université Blaise Pascal et une Habilitation à Diriger des Recherches en 2002 à l’Université de Technologie de Compiègne. Depuis 2004, il est Professeur à l'UTC où il est actuellement responsable de la filière ADEL (Aide à la Décision En Logistique) au département de Génie Informatique et responsable de l’équipe (Réseaux & Optimisation) de l’Unité Mixte de Recherche CNRS, Heudiasyc. Il est auteur de nombreuses publications internationales en recherche opérationnelle. Son domaine d'intérêt est l'optimisation combinatoire, et plus spécifiquement, les problèmes d'ordonnancement et de tournées de véhicules.
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.
BIO-SKETCH
Benoît OTJACQUES is leading the e-Science Unit of LIST. He received his diploma in Computational Engineering from the University of Louvain (Belgium) and his PhD in Computer Sciences from the University of Namur (Belgium). He also studied innovation management, strategic intelligence, IT law in various Universities from France and Belgium. For more than a decade he has been studying information visualization and visual analytics. In the last years he has focused the activities of his team on the applications in the environmental domains (e.g. bioenergy, water management, space applications...). He has (co-)authored more than 70 peer-reviewed scientific papers.
