24.06.2019 Presentation at EURO 2019 (Dublin): "Generating Hard Instances for Robust Optimization"
Joint work with Stephen Maher
Our plan is to collect a wide variety of hard robust optimization instances, and to make them available to the research community via a
dedicated webpage, “www.robust-optimization.com”.
20.06.2019 New preprint available: "Flexible here-and-now decisions for two-stage multi-objective optimization: Method and application to energy system design selection"
In this paper, we propose the flexible here-and-now decision (flex-hand) approach for automatic identification of one single design for multi-objective optimization. The approach minimizes the distance of the Pareto front based on one fixed design to the Pareto front allowing multiple designs. Uncertainty regarding parameters of future operations can be easily included through a robust extension of the flex-hand approach.
Results of a real-world case study show that the obtained design is highly flexible to adapt operation to the considered objective functions. Thus, the design provides an energy system with the ability to adapt to a changing focus in decision criteria, e. g., due to changing political aims.
08.05.2019 New preprint available: "Robust two-stage combinatorial optimization problems under convex uncertainty"
In this paper a class of robust two-stage combinatorial optimization problems is discussed. It is assumed that the uncertain second stage costs are specified in the form of a convex uncertainty set, in particular polyhedral or ellipsoidal ones. It is shown that the robust two-stage versions of basic network and selection problems are NP-hard, even in a very restrictive cases. Some exact and approximation algorithms for the general problem are constructed. Polynomial and approximation algorithms for the robust two-stage versions of basic problems, such as the selection and shortest path problems, are also provided.
02.04.2019 EJOR Award for Excellence in Reviewing 2019
Prof. Dr. Marc Goerigk won the "Editors' Award for Excellence in Reviewing 2019" awarded by the European Journal of Operational Research in recognition of an outstanding contribution to the quality of the Journal in 2018.
01.04.2019 Miriam Kuhrt joins the team
Ms Herrmann has left our team, so Ms Kuhrt is now the new team administrator of the Network and Data Science Management Chair. For more Information see Team Admin.
21.02.2019 Robust optimization workshop in September
In September 19th and 20th 2019 a workshop on robust optimization takes place at the University of Siegen. Registrations are open now. More information can be found here.
14.02.2019 www.robust-optimization.com is online!
We are proud to announce the launch of a new website, www.robust-optimization.com. Over the next months, our aim is to develop a hub for benchmark instances in robust optimization. The first set of instances are already online, based on the method described in our recent paper.
Community-based contributions are welcome!
11.01.2019 New preprint available: "A comparison of Models for Uncertain Network Design"
To solve a real-world problem, the modeler usually needs to make a trade-off between model complexity and usefulness. This is also true for robust optimization, where a wide range of models for uncertainty, so-called uncertainty sets, have been proposed. However, while these sets have been mainly studied from a theoretical perspective, there is little research comparing different sets regarding their usefulness for a real-world problem.
In this paper we consider a network design problem in a telecommunications context. We need to invest into the infrastructure, such that there is sufficient capacity for future demand which is not known with certainty. There is a penalty for an unsatisfied realized demand, which needs to be outsourced. We consider three approaches to model demand: using a discrete uncertainty set, using a polyhedral uncertainty set, and using the mean of a per-commodity fitted zero-inflated uniform distribution. While the first two models are used as part of a robust optimization setting, the last model represents a simple stochastic optimization setting. We compare these approaches on an efficiency frontier real-world data taken from the online library SNDlib and observe that, contrary to current research trends, robust optimization using the polyhedral uncertainty set may result in less efficient solutions.
19.12.2018 New preprint available: "Two-stage Combinatorial Optimization Problems under Risk"
In this paper a class of combinatorial optimization problems is discussed. It is assumed that a solution can be constructed in two stages. The current first-stage costs are precisely known, while the future second-stage costs are only known to belong to an uncertainty set, which contains a finite number of scenarios with known probability distribution. A partial solution, chosen in the first stage, can be completed by performing an optimal recourse action, after the true second-stage scenario is revealed. A solution minimizing the Conditional Value at Risk (CVaR) measure is computed. Since expectation and maximum are boundary cases of CVaR, the model generalizes the traditional stochastic and robust two-stage approaches, previously discussed in the existing literature. In this paper some new negative and positive results are provided for basic combinatorial optimization problems such as the selection or network problems.
12.12.2018 New preprint available: "Mixed Uncertainty Sets for Robust Combinatorial Optimization"
In robust optimization, the uncertainty set is used to model all possible outcomes of uncertain parameters. In the classic setting, one assumes that this set is provided by the decision maker based on the data available to her. Only recently it has been recognized that the process of building useful uncertainty sets is in itself a challenging task that requires mathematical support.
In this paper, we propose an approach to go beyond the classic setting, by assuming multiple uncertainty sets to be prepared, each with a weight showing the degree of belief that the set is a "true" model of uncertainty. We consider theoretical aspects of this approach and show that it is as easy to model as the classic setting. In an extensive computational study using a shortest path problem based on real-world data, we auto-tune uncertainty sets to the available data, and show that with regard to out-sample performance, the combination of multiple sets can give better results than each set on its own.
4.12.2018 The team moves
02.11.2018 New preprint available: "Generating Hard Instances for Robust Combinatorial Optimization"
While research in robust optimization has attracted considerable interest over the last decades, its algorithmic development has been hindered by several factors. One of them is a missing set of benchmark instances that make algorithm performance better comparable, and makes reproducing instances unnecessary. Such a benchmark set should contain hard instances in particular, but so far, the standard approach to produce instances has been to sample values randomly uniformly.
In this paper we introduce a new method to produce hard instances for min-max combinatorial optimization problems, which is based on an optimization model itself. Using the Selection problem as an example, we show that it is possible to produce instances which are ten times as hard to solve on average for a state-of-the-art mixed-integer programming solver.
25.9.2018 Guest lectures
In September, Pawel Zielinski and Adam Kasperski from Wroclaw University of Technology will be guests at University of Siegen. Pawel points to "Risk averse single machine scheduling - complexity and approximation", Adam will speak about "Robust two-stage combinatorial problems". The lectures will take place in room US-A 223 from 3 to 4 pm.