Max-Planck-Institut für Informatik, Saarbrücken, Germany
Network Flow and Equilibrium Computation in the Linear Exchange Economy
Friday (Sept. 2), 13:45-15:00 - Aula
Leon Walras introduced an economic market model in 1874. In this model, every agent participating in the market has an initial endowment of some goods and a utility function over sets of goods. Goods are assumed to be divisible.
The market clears at a set of prices if each agent can spend its entire budget (= the total value of its goods at the set of prices) on a bundle of goods with maximum utility, and all goods are completely sold. Market clearing prices are also called equilibrium prices. In the linear version of the problem, all utility functions are linear. For the case of linear utility functions, Walras' model is also known as the linear exchange economy.
Walras argued the existence of equilibrium prices by describing an iterative improvement algorithm. However, his argument was incomplete. A convincing proof of existence was only given in the 1950 by Arrow and Debreu. The proof is non-constructive. Starting in the '70s, the quest for algorithms arose. The first algorithms were exponential. Later, polynomial time algorithms were derived based on the formulation of the problem as a convex program and the use of the Ellipsoid or the interior point method.
In the technical part of the talk, we describe a combinatorial polynomial-time algorithm for computing equilibrium prices. We formulate the problem as a network flow problem in which the prices are modeled as capacities. We show that the problem can be solved by an iterative algorithm. In each iteration, we first adjust the prices and then compute a maximum flow. The adjustment of the prices is based on a careful examination of the current maximum flow.
We also report on an implementation of the algorithm.
(joint work with Ran Duan, Jugal Garg, and Omar Darwish).
Kurt Mehlhorn is a Director of the MPI for Informatics and Professor of Computer Science at Saarland University. He heads the algorithms and complexity group at the MPI for Informatics. He co-authored some 300 publications in the field, published six books, and is one of the people behind the LEDA software library. He graduated more than 80 students, many of whom have now faculty positions. He has received several prizes (Leibniz Award, EATCS Award, ACM Paris Kanellakis Theory and Practice Award, Erasmus Medal of the Academia Europaea) for his work. He holds Honorary Doctorate Degrees from Magdeburg, Waterloo, Aarhus and Gothenburg universities and is an ACM Fellow. He is a member of the German Academy of Sciences Leopoldina, Academia Europaea, the German Academy of Science and Engineering acatech, the US Academy of Engineering, and the US Academy of Science. From 2002 to 2008, he was vice president of the Max Planck Society. He is a co-founder of Algorithmic Solutions Software GmbH.
Perspectives on Research in Humanitarian Operations
Wednesday (Aug. 31), 09:00-10:30 - Aula
Research in Humanitarian Operations has increased exponentially in recent years with hundreds of papers, several books and quite a few survey articles. At the same time, the problems faced by humanitarian organizations have grown in complexity. Their case load has increased substantially and funding is being reduced. The type and frequency of disasters changes (e.g. due to climate change and urbanization) and technology offers new perspectives (e.g. social media or drones). It is therefore important to ask the question whether current research is relevant and impactful, and what are burning research questions.
Humanitarian Operations take place in specific contexts that are often very different from commercial operations: destroyed infrastructure, failing information systems, insufficient funds and assets, dynamic and chaotic situations, multiple stakeholders with diverging objectives, conflicts and fighting parties, security issues, and so on. It is therefore crucial to understand the impact these contextual elements may have on the problem at hand and whether our standard OR tools are readily applicable or not. In many cases, they are not, i.e. new approaches and perhaps methodologies are needed. In short, a new science of humanitarian operations needs to be developed to provide support in conditions where our classical tools simply do not apply.
The first principle of humanitarian operations is “Do no harm”. It is very tempting to use our classical OR tools and state the results will help humanitarians. The truth, however, is that without proper knowledge of the context, the outcomes of our tools can easily be misleading or even downright wrong. Context is important and in this research area, perhaps more than in many other ones, it is fundamental to carefully check assumptions, data, method, and output with humanitarian experts, to triangulate things and verify results and potential impact before making strong claims or recommendations.
This presentation will attempt to present the specific context of humanitarian operations, introduce some key issues and research questions, and illustrate these with some examples from successful studies.
Professor Van Wassenhove's recent research focus is on closed-loop supply chains (product take-back and end-of-life issues) and disaster management (humanitarian logistics). He publishes regularly in Management Science, Production and Operations Management, and many other academic as well as management journals (like Harvard Business Review, and California Management Review). He is the author of many award-winning teaching cases and regularly consults for major international corporations. In 2005, Professor Van Wassenhove was elected Fellow of the Production and Operations Management Society (POMS). In 2006, he was the recipient of the EURO Gold Medal for outstanding academic achievement. In 2009 he was elected Distinguished Fellow of the Manufacturing and Services Operations Management Society (MSOM), and received the Lifetime Achievement Faculty Pioneer Award from the Academy of Business in Society (ABIS) and the Aspen Institute. In 2013 he became Honorary Fellow of the European Operations Management Association (EurOMA). He is a member of the Royal Flemish Academy of Sciences. Before joining INSEAD he was on the faculty at Erasmus University Rotterdam and Katholieke Universiteit Leuven. At INSEAD he holds the Henry Ford Chair of Manufacturing. He created the INSEAD Social Innovation Centre and acted as academic director until September 2010. He currently leads INSEAD’s Humanitarian Research Group.
Dynamic pricing with forward-looking consumers
Thursday (Sept. 1), 13:30-14:15 - Hörsaal 2
Determining effective pricing policy when selling to strategic consumers that arrive over time is a growing area that is posing challenging questions with practical implications. In this talk we study a basic pricing problem in which a single unit is on sale and consumers are forward looking. We first discuss a model in which the price can only change at discrete times. Then, we derive optimal pricing schemes for the case in which the price can change continuously. All these pricing schemes require that the seller has commitment power. This is an important assumption that we discuss in detail.
Jose Correa is a Professor of Industrial Engineering at Universidad de Chile. He graduated as a Mathematical Engineer from Universidad de Chile in 1999 and obtained a PhD in Operations Research from MIT in 2004. His research, focusing in combinatorial optimization and game theory, has been rewarded with some important prizes (such as the TSL best paper award, Tucker prize finalist). Jose serves in the editorial board of Operations research and Mathematical Programming B and has been in the PC of a number of conferences.
University of Twente, The Netherlands
Decentralized Energy Management: New Challenges for Operations Research
Thursday (Sept. 1), 13:30-14:15 - Hörsaal 3
Our energy systems undergo a fundamental change. Where in the past the energy mainly was generated in large power plants using fossil fuels, in the future a large part of the generation will result from small plants in decentralized locations using uncontrollable renewable sources. This leads to a loss of control over a larger fraction of the generation. To be able to compensate for this loss in flexibility on the generation side, we have to create and use flexibility on the consumption side. This has led to the concept of ‘Smart Grids’ and ‘Decentralized Energy Management’ is seen as a key element for these Smart Grids.
In this talk we first give an overview of the relevant developments in the Energy Supply Chain. Based on the changes we sketch possible concepts and methods for future control of these supply chains. Hereby Decentralized Energy Management is seen as one of the key elements. In a second part, we argue that devices with inherent storage offer large portions of flexibility and discus a range of scheduling problems that come up for these devices. For a few of these problems we sketch possible solution approaches.
Johann L. Hurink received the Ph.D. degree from University of Osnabrück (Germany) in 1992 for a thesis on a scheduling problem occurring in the area of public transport. From 1992 until 1998 he has been an assistant professor at the same university working on local search methods and complex scheduling problems. This work resulted in a Habilitation thesis at the University of Osnabrück in 1999.From 1998 until 2009 he has been an assistant and associated professor in the group Discrete Mathematics and Mathematical Programming at the department of Applied Mathematics at the University of Twente.
Since 2009 he is a full professor of the same group and since 2010 also the Director of the Dutch Network on the Mathematics of Operations Research (LNMB). He has published more than 100 refereed papers in international journals and conferences and has been involved in several European and national research projects. Current work includes the application of optimization techniques and scheduling models to problems from decentralized energy management, logistics, and health care.
Revenue Management: Selected Concepts and Applications
Friday (Sept. 2), 11:00-11:45 - Hörsaal 1
During the last three decades, Revenue Management has evolved into one of the most important fields of application of Operations Research.
Basically, it is concerned with the task of optimally selling a fixed capacity of perishable resources within a given booking horizon, thereby maximizing the overall profit or contribution. This is essentially achieved by the application of two instruments: In a first step, *price differentiation* is performed, leading to a variety of differently priced products defined on the set of available resources. In a second step, the availability of these products is permanently adjusted by means of *capacity control* according to the current forecast of future demand. Beyond generating theoretical results concerning methods for capacity control, new concepts for modeling demand have been introduced recently and new application areas are emerging. To reflect these developments, this talk provides an overview on all three topics.
Examples from well-known application areas like the airline industry, but also from recent ones like e-fulfillment are discussed.
After both, studying Business Administration and Information Systems as well as working as a research assistant at the Technical University of Darmstadt, Robert Klein became a full Professor at the University of Augsburg in 2006. There he holds the chair for Analytics & Optimization, representing the first chair in Germany being explicitly devoted to the trend toward more data, more algorithmic analysis of it, and more orientation to model-based and fact-based decision making.
Robert has been involved in research and development in the areas of pricing and revenue management, analytical customer relationship management, and operations research. He is excited in solving real-world problems by analytics and, therefore, is very much interested in transferring results of his team's research to industry. In recent years, he has done projects in cooperation with Daimler, IBM, Lufthansa Systems, Sixt, and TUI, with most of the projects having a strong emphasis on analytical pricing. He has published in journals such as Computers & Operations Research, European Journal of Operational Research, INFORMS Journal on Computing, Omega, OR Spectrum, or Transportation Science. Furthermore, he is the co-author of several textbooks on business mathematics, operations research, and revenue management.
Lund University, Sweden
Sustainable Supply Chain Inventory Control
Wednesday (Aug. 31), 15:30-16:15 - Hörsaal 3
The increasing environmental awareness drives a growing interest among companies for more sustainable supply chain operations. One important challenge is to reduce transportation emissions while minimizing total inventory and transportation costs for multi-stage systems. In this talk different aspects of this challenge are considered for distribution systems where a central warehouse replenishes a number of local warehouses or retailers. Particularly, we present a multi-echelon inventory control model incorporating volume dependent freight costs and emissions, shipment consolidation, and intermodal transport options. To emphasize the importance of a multi-stage perspective, we also present results from a simulation study of a Scandinavian spare parts provider with frequent use of emergency deliveries. It illustrates that applying a multi-echelon inventory control method can significantly reduce total inventories and transport emissions while improving fulfillment of target fill-rates.
Johan Marklund is Professor of Production Management at Lund University, Faculty of Engineering, in Sweden. He has previously worked at the Leeds School of Business, University of Colorado, Boulder, and the Boston Consulting Group. He holds degrees from Linköping University (MSc), and Lund University (BSc and PhD). His research interests include inventory theory, supply chain management and logistics. A special emphasis is placed on stochastic multi-echelon inventory problems, lately with applications in the sustainability area with focus on integrated control of inventory and transportation decisions.
University of Jyväskylä, Finland
Advantages of Interactive Multiobjective Optimization Methods Demonstrated with NAUTILUS Navigator enabling Navigation without Trading-Off
Wednesday (Aug. 31), 15:30-16:15 - Hörsaal 1
Multiobjective optimization is needed because most real-life optimization problems contain more than one objective function. The goal in multiobjective optimization is to find the best possible solution in the presence of several, conflicting objective functions. Using mathematical tools we can define a set of Pareto optimal solutions where none of the objective function values can be improved without impairing at least
one of the others. However, we need additional preference information from a domain expert, a decision maker, to find the most preferred Pareto optimal solution as the final solution to be implemented. Multiobjective optimization methods can be classified according to the role of the decision maker in the solution process. We concentrate on interactive methods, where the decision maker takes actively part in the solution process and directs the search for the final solution according to her/his desires and hopes. This enables the decision maker to gain insight about the interdependencies of the conflicting objectives and learn about one's own preferences.
Typically, interactive methods deal with Pareto optimal solutions only and the decision maker must trade-off to be able to move from one Pareto optimal solution to another. To avoid this need of trading-off, a family of NAUTILUS methods has been proposed. In NAUTILUS, the interactive solution process begins from an inferior solution and the decision maker can gain improvement in all objective functions and direct the solution process until (s)he reaches the set of Pareto optimal solutions. In this way, (s)he can move more freely without anchoring around any solution. We introduce a new method called NAUTILUS Navigator which incorporates the NAUTILUS philosophy with elements of the Pareto Navigator method. With NAUTILUS Navigator, the decision maker can navigate in real time towards the set of Pareto optimal solutions and continuously see how the region of objective function values that are reachable without trading-off shrinks. The distance to the set of Pareto optimal solutions is also shown. Thanks to the graphical user interface, the information is available in an understandable form. The decision maker can provide preference information to direct the movement as desirable aspiration levels and bounds that are not to be exceeded. The decision maker can change the navigation direction at any time and even go backwards if needed.
The NAUTILUS Navigator method is also applicable to computationally expensive problems where function evaluations are time-consuming. We demonstrate how the method can be applied with a three-objective optimization problem for identifying the improvements that can be carried out in the auxiliary services of a power plant in order to enhance its efficiency, taking into account energy savings and economic criteria.
Kaisa Miettinen is Professor of Industrial Optimization at the Department of Mathematical Information Technology, University of Jyvaskyla in Finland. She is also vice-rector of the University of Jyvaskyla. In this position she chairs the science council and the graduate school for doctoral studies. She received her Ph.D. and M.Sc. degrees at the Department of Mathematics of the University of Jyvaskyla in 1994 and 1988, respectively. Her research interests include theory, methods, applications and software of nonlinear multiobjective optimization including interactive and evolutionary approaches and she heads the Research Group on Industrial Optimization. She has authored about 150 refereed journal, proceedings and collection papers and over 80 reports, edited 13 proceedings, collections and special issues (and one special issue is in preparation) and written a monograph Nonlinear Multiobjective Optimization. She is the Immediate-Past President of the International Society on Multiple Criteria Decision Making and has also chaired EUROPT, the EURO Working Group on Continuous Optimization and the Finnish Operations Research Society. She belongs to the editorial boards of six international journals and is subject editor in mathematics of the journal Optimization and Engineering. She belongs to the Steering Committee of Evolutionary Multi-Criterion Optimization and is a member of the IEEE Computational Intelligence Society Task Force Group on Multiobjective Evolutionary Algorithms. She has worked at IIASA, International Institute for Applied Systems Analysis in Austria, KTH Royal Institute of Technology in Stockholm, Sweden and at Helsinki School of Economics in Finland.
She was the Chair of the 21st International Conference on Multiple Criteria Decision Making in 2011. She was the program chair of the 23rd International Conference on Multiple Criteria Decision Making which was held in Hamburg in 2015. She has also been the co-organizer of four Dagstuhl seminars devoted to fostering collaboration between multiple criteria decision making and evolutionary multiobjective optimization researchers. She is a member of the Finnish Academy of Science and Letters, Section of Science, she has been awarded the Väisälä Award of the Finnish Academy of Science and Letters in the field of mathematics in 2009 and she was chosen as Researcher of the Year at Helsinki School of Economics in 2007. For further information, see here.
Stochastic Programs in Gas and Power Networks
Friday (Sept. 2), 11:00-11:45 - Hörsaal 2
Up to fairly recently, power and gas suppliers have been at the sunny side, both technologically and politically. Due to market regulation, the economic actions of these companies were taken almost ``with complete information'' under granted sales prices. Some uncertainty remained regarding power and gas demand.
But this comes close to nothing when looking at it from today's perspective: Deregulation led to unbundling of activities and, as a consequence, unbundling of knowledge on data. While before minimization of fuel costs for gas compression clearly dominated other expences, it is the slogan of today to deliver gas to the right place at the right time in the right quantitity, and with the right quality.
Mathematical models facing these new developments will provide the guidelines for this lecture. A particular role will be taken by mild nonlinearities and their handling with both techniques from polynomial algebra and analysis.
Rüdiger Schultz is a Full Professor for Discrete Mathematics and Optimization in the Department of Mathematics at the University of Duisburg-Essen, Germany, since 1998. His doctoral and habilitation degrees in Mathematics he has received from the Humboldt University Berlin in 1985 and 1995. Dr. Schultz' primary research interests are in optimization under uncertainty, discrete optimization, and in industrial applications of mathematical optimization. His research accomplishments include seminal results on structure, stability, and algorithmic treatment of stochastic programs, in particular of models involving integer variables, risk aversion, and, more recently, also PDE constraints. He has made contributions to real-life applications of mathematical optimization in the power, natural gas, and chemical processes industries. He has co-authored more than 100 scientific papers. Currently, Dr. Schultz is Editor-in-Chief of the journal "Computational Management Science" and Area Editor Linear and Stochastic Optimization of "Operations Research Letters". He is serving as a member of the editorial boards of five further research journals in mathematics.
University of Antwerp, Belgium
A history of metaheuristics
Friday (Sept. 2), 11:00-11:45 - Hörsaal 5
Even though people have used heuristics throughout history, and the human brain is equipped with a formidable heuristic engine to solve an enormous array of challenging optimization problems, the study of heuristics (and by extension metaheuristics) is a relatively young endeavour. It is not an exaggeration to claim that the field of (meta)heuristics, especially compared to other fields of study like physics, chemistry, and mathematics, has yet to reach a mature state. Nevertheless, enormous progress has been made since the first metaheuristics concepts were established. In this talk, we will attempt to describe the historical developments this field of study has gone through since its earliest days.
Taking a bird's eye view of the field of metaheuristics, one has to conclude that there has been a large amount of progressive insight over the years. Moreover, this progressive insight has not reached its end point: the way researchers and practitioners look at metaheuristics is still continually shifting. In our view, it is this shifting paradigm that deserves attention, as it allows us to truly understand the past and perhaps learn a few lessons that could be useful for the future development of research in metaheuristics.
No history is ever completely neutral. We therefore do not attempt to hide the fact that certain ways in which the field has been progressing seem less useful, and sometimes even harmful to the development of the field in general. It is our conviction that the metaheuristics community itself is, at least partially, to blame for this. We will therefore also touch on some ways in which more scientific hygiene can be introduced in metaheuristics research. Nevertheless, a preliminary conclusion is that the field of metaheuristics has been steadily progressing towards becoming a mature field of research, and will continue to do so in the foreseeable future.
Kenneth Sörensen is professor at the Faculty of Applied Economics of the University of Antwerp, where he also obtained his PhD. Kenneth Sörensen chairs the research group ANT/OR (University of Antwerp Operations Research Group), a group that focuses on applications of Operations Research in diverse domains, and on the development of optimization algorithms, especially metaheuristics.
Kenneth Sörensen has published extensively on applied (heuristic) optimization and is a leading expert on the development of metaheuristics. He also founded the largest working group on metaheuristics: EU/ME - the metaheuristics community.
Katholieke Universiteit Leuven, Belgium
Scheduling a soccer league
Thursday (Sept. 1), 13:30-14:15 - Hörsaal 5
Soccer has become a major business involving many stakeholders, such as teams, police, fans, sponsors, and broadcasting companies. Huge amounts of money are being paid for the broadcasting rights, illustrating the economic value of soccer competitions. It also emphasizes the relevance of finding a good schedule. Each involved party has numerous (possibly conflicting) constraints and wishes, and a schedule that satisfies all constraints and wishes simply doesn't exist. Hence, developing a schedule that is considered fair, and that is acceptable to all parties, is a challenge.
We describe our experience in scheduling the ProLeague, Belgium’s highest professional league, over the last seasons. We outline some of the different models we used, and we emphasize the advantages of using model-based schedules: transparency, perceived fairness, or simply said: the quality of the schedule.
Frits Spieksma is a professor of Operations Research at the Faculty of Business and Economics of KU Leuven (Belgium). He is interested in combinatorial optimization problems, both from a theoretical point of view, as well as from a practical point of view. He has a specific interest in sport scheduling problems, and initiated a EURO Working Group on this subject. He has coauthored over 80 research papers, and serves on the board of several OR journals.
OR for Future Mobility: Designing Sustainable Means of Transportation
Thursday (Sept. 1), 13:30-14:15 - Hörsaal 1
The transportation sector contributes significantly to global fossil CO2 emissions, and is still almost totally reliant on petroleum-derived fuels. Therefore, a transformation is needed and sustainable means of transportation have to be launched and disseminated. In this context, strategic investment decisions have to be taken, e.g. regarding the installation of charging infrastructure for battery electric vehicles or the design of production networks and supply chains for biofuels and E-fuels. Additionally, complex planning problems arise at an operational level, e.g. by routing battery electric vehicles with limited range and need for (partial) recharging in a still scarce infrastructure, or by integrating load management of the electricity grid with charging of large electric vehicle fleets.
This talk will give an overview on how OR can contribute to solve these new challenges in the transportation sector. Examples on projects will be given, current challenges will be discussed, and requirements for OR models will be derived. Some of the models and applications will be discussed in more detail, and insights on how these approaches can be implemented in practice will be given.
Grit Walther holds a Diploma in Geoecology (1999) and a PhD in Business Administration (2004) from Technische Universität Braunschweig. In 2009 she finished her habilitation with a thesis on “Sustainable Supply Chains”. After being professor for Production and Logistics at Bergische Universität Wuppertal (2010 to 2012), she is since 2012 full professor and head of the Chair of Operations Management at RWTH Aachen University.
Her research focuses on application-oriented, techno-economic modelling and evaluation of logistics and production systems as well as supply chains with specific emphasize on sustainability aspects. Current research topics are network planning for recycling and reverse logistics systems, design and management of sustainable supply chains, as well as design of sustainable mobility systems.
Grit Walther is member of the strategy board of RWTH Aachen University, head of the scientific commission on "Sustainability Management" of the VHB and coordinating board member of the EURO Working Group on "Sustainable Supply Chains".
Eindhoven University of Technology, The Netherlands
New answers to old questions on the TSP
Wednesday (Aug. 31), 15:30-16:15 - Hörsaal 2
k-OPT is one of the most popular local search heuristics for the Travelling Salesman Problem (TSP). k-OPT tries to improve a suboptimal tour by removing k of the edges and by reconnecting the resulting tour pieces into a new tour by inserting k new edges.
In the talk, I will mainly concentrate on the question whether a given tour is a local optimum for k-OPT (where k is some fixed, small number), and I will present a fine-grained complexity analysis of this problem.
Gerhard J. Woeginger is a professor at the Eindhoven University of Technology, where he chairs the combinatorial optimization group in the department of mathematics and computer science. His research interests lie in the intersection area of Operations Research, Theoretical Computer Science, and Discrete Mathematics.
Woeginger was program chair of the European Symposium on Algorithms (ESA-1997), the International Colloquium on Automata, Languages and Programming (ICALP-2003), the European Conference on Operational Research (EURO-2009), the International Computer Science Symposium in Russia (CSR-2016), and of several other conferences. He received a Humboldt Research Award in 2011, and he was elected to the Academia Europaea in 2014.