ESSEC Business School, Paris
From Game Theory to Graph Theory: A Bilevel Journey
In bilevel optimization there are two decision makers, commonly denoted as the leader and the follower, and decisions are made in a hierarchical manner: the leader makes the first move, and then the follower reacts optimally to the leader’s action. It is assumed that the leader can anticipate the decisions of the follower, hence the leader optimization task is a nested optimization problem that takes into consideration the follower’s response.
In this talk we focus on new branch-and-cut (B&C) algorithms for dealing with mixed-integer bilevel linear programs (MIBLPs). We first address a general case in which intersection cuts are used to cut off infeasible solutions. We then focus on a subfamily of MIBLPs in which the leader and the follower share a set of items, and the leader can select some of the items to inhibit their usage by the follower. Interdiction Problems, Blocker Problems, Critical Node/Edge Detection Problems are some examples of optimization problems that satisfy the later condition. We show that, in case the follower subproblem satisfies monotonicity property, a family of “interdiction-cuts” can be derived resulting in a more efficient B&C scheme.
These new B&C algorithms consistently outperform (often by a large margin) alternative state-of-the-art methods from the literature, including methods that exploit problem specific information for special instance classes.
Ivana Ljubic is Professor of Operations Research at the ESSEC Business School of Paris. She holds habilitation in Operations Research from the University of Vienna (2013) and a PhD degree in Computer Science from the Vienna University of Technology (2004). Research interests of Ivana Ljubic include network design problems, combinatorial optimization, optimization under uncertainty, bilevel optimization. She uses tools and methods of mixed integer programming, (meta-)heuristics and their successful combinations for solving large-scale optimization problems with applications in telecommunications, logistics, design of data and distribution networks, or bioinformatics. She was awarded: DOC and APART fellowships of the Austrian Academy of Sciences, Hertha-Firnberg fellowship of FWF and PhD-award of the Austrian Society for Operations Research. She is currently vice-president of the INFORMS Telecommunication Section and serves as a board member of several leading journals in Operations Research.
Leiden Institute of Advanced Computer Science (LIACS), Universiteit Leiden
Learning how to solve it - faster, better and cheaper
We stand on the threshold of an AI revolution, where explicit programming as the fundamental paradigm for algorithmic problem solving is being replaced by increasingly automated approaches. Specifically, methods from generalised machine learning not only dramatically increase our ability to solve challenging computational problems, they also bring about a fundamental change in the way in which we design and deploy algorithms and software. In this talk, I will examine the nature of this change and its consequences, and I will give examples of the meta-algorithmic techniques that enable it. Specifically, I will discuss algorithm selection and configuration techniques, auto-tuning and the increasingly impactful area of automated machine learning (AutoML). Using examples from mixed integer programming, combinatorial optimisation and propositional reasoning, I will demonstrate the impact of these techniques, in terms of the results they achieve, as well as with respect to the way we approach these and other computational challenges.
Holger H. Hoos is Professor of Machine Learning at Universiteit Leiden (the Netherlands) and Adjunct Professor of Computer Science at the University of British Columbia (Canada), where he also holds an appointment as Faculty Associate at the Peter Wall Institute for Advanced Studies. He is a Fellow of the Association for the Advancement of Artificial Intelligence (AAAI) and past president of the Canadian Association for Artificial Intelligence / Association pour l’intelligence artificielle au Canada (CAIAC).
Holger’s research interests span artificial intelligence, empirical algorithmics, bioinformatics and computer music. He is known for his work on machine learning and optimisation methods for the automated design of high-performance algorithms and for his work on stochastic local search. Based on a broad view of machine learning, he has developed - and vigorously pursues - the paradigm of programming by optimisation (PbO); he is also one of the originators of the concept of automated machine learning (AutoML). Holger has a penchant for work at the boundaries between computing science and other disciplines, and much of his work is inspired by real-world applications.
GERAD & Polytechnique Montreal
Optimizing the future of smart grids
A smart grid is the combination of a traditional electrical power system with information and energy both flowing back and forth between suppliers and consumers. This new paradigm introduces major challenges such as the integration of decentralized energy generation, the increase of electric transportation, and the need for electricity consumers to play an active role in the operations of the grid. This presentation will summarize the opportunities for optimization to contribute to the success of smart grids and present some recent breakthroughs.
Miguel F. Anjos is Full Professor in the Department of Mathematics and Industrial Engineering of Polytechnique Montreal, where he holds the NSERC-Hydro-Quebec-Schneider Electric Industrial Research Chair on Optimization for the Smart Grid, and the Inria International Chair on Power Peak Minimization for the Smart Grid. He received the B.Sc. degree from McGill University, the M.S. from Stanford University, and the Ph.D. degree from the University of Waterloo. His research interests are in the theory, algorithms and applications of mathematical optimization. He is particularly interested in the application of optimization to problems in power systems management and smart grid design. He is the Founding Academic Director of the Trottier Institute for Energy at Polytechnique, which he led from its inauguration in May 2013 until August 2016. He served as Editor-in-Chief of Optimization and Engineering, and serves on several other editorial boards. He was elected to three-year terms on the Council of the Mathematical Optimization Society and as Program Director for the SIAM Activity Group on Optimization, and to a two-year term as Vice-Chair of the INFORMS Optimization Society. He served on the Mitacs Research Council since its creation in 2011 until 2017, and is now an Emeritus member. His allocades include IEEE Senior Membership, a Canada Research Chair, the Méritas Teaching Award, a Humboldt Research Fellowship, the title of EUROPT Fellow, and the Queen Elizabeth II Diamond Jubilee Medal. He is a fellow of the Canadian Academy of Engineering.
Université Grenoble Alpes
A community of teachers for an active pedagogy in OR
Caseine is a learning platform (caseine.org). Its aim is to stimulate students’ learning and autonomy while improving the quality of the time the teacher gives them. Based on Moodle, it allows to
We present some use cases of Caseine, specially in Linear Programming and Graph Theory. For instance, we explain how the linear programming models are evaluated automatically on the plateform and how the activities are shared between the teachers of various universities.
Caseine offers a connexion for all users in Edugain who can connect via their own university. With this connexion, you can test the Operations Research open course. We will present how to join the OR teacher community on Caseine and create your own courses while using and contributing to the shared activities.
Nadia Brauner is a professor of Computer Science at Université Grenoble Alpes in France. Her research focuses mainly on theoretical scheduling and on practical applications of Combinatorial Optimization in Operations Research (OR). She was president of the French OR society (ROADEF). She is responsible for OR and Combinatorial Optimization courses in the Computer Science and Applied Mathematics programs at Université Grenoble Alpes. She is head of the caseine.org platform.
University of Vienna
Collaboration in Vehicle Routing
Carrier collaboration is one of the big trends in transportation. Exchanging transportation requests between carriers can reduce inefficiencies and generate economic and ecologic benefits for the partners as well as for the society. In horizontal logistics collaboration, several companies exchange some of their transportation requests in order to execute them more efficiently. The forming of these coalitions is commonly realized by using auction-based exchange mechanisms. In combinatorial auctions, requests are not traded individually but are combined into packages, called bundles. The main reason for this is that a bundle might have a different (typically higher) value to the partners than the sum of the individual requests. We discuss the five typical phases in combinatorial transportation auctions: First, the carriers select request that they want to auction-off (request selection), then the auctioneer generates bundles of requests and offers them to the participants (bundling). These give their bids on offered bundles by calculating the marginal profit of each bundle (bidding). Finally, requests are allocated to carriers according to their bids, so that the total profit for the coalition is maximized (winner determination). Gained profits are distributed among the carriers (profit sharing). All five phases result in challenging optimization problems.
Richard Hartl is a full Professor of Production and Operations Management at the University of Vienna. He holds a PhD degree in Mathematics from the and also obtained his habilitation in Operations Research from the Vienna University of Technology. He was Post-Doctoral Fellow at the University of Toronto, full Professor at the OvG University Magdeburg (Germany) and guest professor at various other universities.
Research interests of Richard Hartl include a variety of areas such as optimal control and dynamic economic models of the firm, as well as applications of discrete optimization in production and operations management. In the last years, one of his main research has been modelling of rich vehicle routing problems and their solution using metaheuristic and hybrid methods. This includes stochastic, multi-objective, and collaborative versions.
He had been treasurer and president of the Austrian OR society and currently is treasurer of the International Federation of Operational Research Societies (IFORS). He has been associate editor of many leading journals in OR and logistics, e.g. Transportation Science.
Optimization, Data Science, and Machine Learning in Car Rental Revenue Management
Revenue Management and Dynamic Pricing methodology was originally developed in the context of passenger aviation facing mounting economic pressure after deregulation of the market. In the context of car rental, other Operations Research techniques, related to production and logistics, were added in. Partly, this is due to the greater operational flexibility in capacity management and fleet relocation. On the other hand, customer requirements with regards to the inventory are more specific: for a premium mobility brand, dozens of relevant car groups have to be offered exactly where and when they are needed. Premium service includes almost unlimited flexibility for the customer, with the option to change plans on short notice, within a large network of rental locations or even whole city areas in a free float mode. Under these conditions, to maintain high levels of utilisation and a competitively priced offer requires advanced forecasting and optimisation techniques. Successful car rental Revenue Management is therefore key to creating customer excitement and loyalty.
In the talk we will give an overview of the evolution of relevant methods. At least as important as the choice of algorithms is the appropriate modelling of economic principles at play, such as opportunity costs, which form the central concept around which most RM systems are designed today. We will also discuss the impact of new forms of mobility on the development of Revenue Management, and the role of Machine Learning technology and of some other concepts from Artificial Intelligence.
Henrik Imhof has been Head of Yield Management and Pricing at Sixt rent-a-car since 2007. From 2002 to 2007 he worked in the revenue management department of Swiss International Airlines, where he helped to shape the concepts for an integrated origin-destination pricing and inventory control, in particular in the field of rule-based dynamic pricing. He had started his airline career in the development and marketing of IT systems for network planning and flight scheduling at SAirGroup. He holds a PhD in Mathematics from the University of Freiburg i. Br. and worked as a research assistant at the University of Wales Swansea (1995 to 1996). At Sixt, Henrik and his team are developing new revenue management tools suited for flexible capacity and for the integration of pricing aspects in a multi-channel and multi-product environment.
RWTH Aachen University
Combinatorial Optimization inspired by Uncertainties
The growing need to deal with uncertainties in optimization processes has lead to many new research directions. In robust optimization, an uncertainty set has to be defined containing all scenarios to be considered. Availability of historical data often suggests the use of a discrete or polyhedral uncertainty set. By this, new combinatorial optimization problems are evolved.
In this talk, we discuss a few examples of novel combinatorial optimization problems inspired by uncertainties in network design and production planning. Further, this talk should motivate research on the additional complexity introduced by uncertainties.
Arie M. C. A. Koster (1973) is a Professor of Discrete Optimization at RWTH Aachen University. Before moving to Aachen in 2009, he was a senior researcher with the Department of Optimization at Zuse Institute Berlin and an Assistant Professor at Warwick Business School and the Centre for Discrete Mathematics and its Applications of the University of Warwick (UK). His research interests include integer linear programming, robust optimization, algorithmic graph theory, and network optimization. He has published over 100 research papers and is an associate editor of both INFORMS Journal of Computing and the Asia-Pacific Journal of Operational Research. Recently, he has been studying application-driven optimization problems such as dayahead energy supply, production scheduling, virtual network embedding, and design of flexgrid optical networks, all under demand uncertainty.
UBw München COMTESSA
Resilience of Complex Networks - Analysis and Optimization of Critical Infrastructures Systems with Executive Towers
Our modern society relies more and more on increasingly interconnected technological infrastructures. Communication systems control terrestrial- and air traffic which requires electrical power supply to assure the logistic of industrial production and consumption of goods. These many mutually dependent networks are vulnerable towards a multitude of external and internal risks.
Therefore, there is a great interest in the understanding of dynamic resilience concepts and the development of adaptive security structures for an holistic risk management. We summarize the main concepts like graph measures, and present actual examples in the field of safety and security via advanced analytics techniques.
We characterize the behavior and present some new optimization approaches which could be embedded in reachback processes. We will explore suitable strategies to make the networks more robust; for example motivated by Moreira in 2009 topological structure optimization, anticipatory strategies and AI instruments are combined in our presentation.
As innovative approach we introduce the concept and characterization of a control tower. In an „executive way“, we control the process and present first numerical results. We present the concept of „Executive Towers“ as basis for a suitable management cockpit.
Stefan Wolfgang Pickl was born in Darmstadt, Germany on 29th September, 1967. He studied mathematics, electrical engineering and philosophy at the Technical University of Darmstadt (Diploma in 1993; ERASMUS-scholarship at the EPFL Lausanne); doctor’s degree at the TU Darmstadt in 1998 followed by his habilitation at the University of Cologne in 2005. From the years 2000 to 2005 Mr Pickl was scientific assistant and project manager at the Center for applied Computer Sciences in Cologne (ZAIK).
In 2000 Mr. Pickl received the phd-thesis award by the German Society for Operations Research; followed by international “best-paper awards” in the years 2003, 2005, 2007 and 2015.
He is board member of the German Committee for Disaster Reduction (DKKV). There, he is mainly engaged in the development of resilient systems and integrated assessment models.
During the years 2004 to 2018 Mr. Pickl was invited for assignments as visiting-professor in the States, Asia and Europe. As a guest scientist Mr Pickl was a “Visiting Scientist” in Los Alamos National Labs, in the SANDIA Laboratory, at the MIT as well as at the Santa Fe Institute for complex systems. He is funding director of COMTESSA (Core Competence Center for Operations Research, Management - Tenacity - Excellence, Safety & Security ALLIANCE).
From 2013-2018 he was international coordinator of the innovative security projects RIKOV and REHSTRAIN (Resilience of the Franco-German High Speed Train Network).
Prof. Dr. Stefan Pickl is Honorary Chair at The University of Nottingham Malaysia Campus.
University of Lisbon
Logistics Network Design and Facility Location: The value of a multi-period stochastic solution
In the past decades Logistics network design has been a very active research field. This is an area where Facility Location and Logistics are strongly intertwined, which is explained by the fact that many researchers working in Logistics address very often location problems as part of the strategic/tactical logistics decisions. Despite all the work done, the economic globalization together with the emergence of new technologies and communication paradigms are posing new challenges when it comes to developing optimization models for supporting decision making in this area. Dealing with time and uncertainty has become unavoidable in many situations.
In this presentation, different modeling aspects related with the inclusion of time and uncertainty in facility location problems are discussed. Emphasis is given to multi-period stochastic programming models. The goal is to better understand problems that are at the core of more comprehensive ones in Logistics Network Design. By considering time explicitly in the models it becomes possible to capture some features of practical relevance that cannot be appropriately captured in a static setting. Additionally, by considering a stochastic modeling framework it is possible to build risk-aware models. Unfortunately, the resulting models are often too large and thus hard to tackle even when using specially tailored procedures. This raises a question: is there a clear gain when considering a more involved model instead of a simplified one (e.g. deterministic or static)? In search for an answer to this question, several measures are discussed that include the value of a multi-period solution and the value of a (multi-stage) stochastic solution. By considering adequate models it is possible to combine the above measures and to quantify the relevance of considering risk in Logistics Network Design.
Francisco Saldanha da Gama is professor of Operations Research at the Department of Statistics and Operations Research at the Faculty of Science, University of Lisbon, where he received his PhD in 2002. He has extensively published papers in scientific international journals mostly in the areas of location theory, supply chain management, logistics and combinatorial optimization. Together with Stefan Nickel, he has been awarded the EURO prize for the best EJOR review paper (2012) and the Elsevier prize for the EJOR top cited article 2007-2011 (2012), both with the paper entitled “Facility location and supply chain management A review”. He is member of various international scientific organizations such as the EURO Working Group on Location Analysis of which he is one the past coordinators. Since 2016 he is Editor-in-Chief of Computers & Operations Research. His research interests include stochastic mixed-integer programming, location theory and project scheduling.
SISRs: An effective ruin & recreate heuristic based on slack induction
Local search approaches have tended towards incorporating an ever-increasing number of made-to-measure heuristics for different problem classes, for example all manner of vehicle routing generalizations. These large heuristic sets consequently present a significant complication for problem solvers, namely: how can one determine the impact of individual heuristic components?
In contrast to targeting generalizing problem extensions, it may be worthwhile to focus on a problem’s core when developing a basic optimization heuristic. This talk introduces a recently developed ruin & recreate heuristic, named SISRs.
While ruin & recreate heuristics may have become widespread, SISRs is unique insofar as it seeks to induce «spatial slack» during its ruin phase which may subsequently be exploited in its greedy recreate phase. Both the crucial «spatial slack» concept and the almost-greedy recreate emerged after a dedicated attempt towards solving the vehicle routing problem’s most basic special case, that is the «capacitated VRP».
SISRs’ quality is validated by way of demonstrating its superior performance across a wide and diverse range of VRP generalizations. This confirms that the basic CVRP ruin & recreate heuristic is also effective when applied to more general problems, without the need to add problem-specific components.
The developed ruin & recreate outperforms current (and often dedicated) state of the art approaches in terms of both speed, robustness and its high-quality results.
Greet Vanden Berghe is a Professor of Computer Science at KU Leuven, Faculty of Engineering Technology. She currently chairs KU Leuven’s Technology Cluster Computer Science and leads one division of the Combinatorial Optimization and Decision Support research group (CODeS) at the Technology Campus Gent.
Her primary research interests are combinatorial optimization and automated decision support, which often lead to the development and implementation of operational systems for a wide range of industrial partners with whom the CODeS research group enjoys close cooperation with. Manufacturing, maritime transportation and health care are a few examples of current active areas. Greet Vanden Berghe’s research has gradually evolved from the modelling of very specific problems towards the development of far more general heuristic solvers which offer an array of real-world applications. Indeed, while more recent optimization problems are far more intricate than their theoretical counterparts - in large part due to the abundance of available data - the demands for solvers follow an entirely opposite trend. They should be flexible, intuitive to use and implementable without the need for considerable setup or tuning effort. These might be challenging goals, but there has been significant progress in terms of achieving them in recent years.