Inhalt des Dokuments
Project B23: Robust Optimization for Network Applications
|Duration:||June 2010 - May 2014|
|Project heads:||Rolf H. Möhring|
|Researcher:||Berit Johannes, (Christina Büsing on leave)|
|Support:||DFG Research Center "Mathematics for Key Technologies" (Matheon)|
Models of real-world problems are always confronted with noisy, incomplete, or erroneous data. An attractive approach for dealing with these variations in data is to include different data sets, also called scenario sets, into the optimization process. Depending on the given situation and information a stochastic approach or a robust approach is then chosen to compute a suitable solution.
Robust optimization provides a high level of security and represents a risk-averse attitude. A solution is called robust if it remains feasible under all considered scenarios. The task is to find a robust solution that minimizes its worst-case cost. The difficulty in robustness is that feasibility under all constraints is quite demanding and may not be achieved by any solution. But even if a robust solution exists, it may produce high cost in many scenarios.
In recent years advanced robust methods have been devised to control conservatism by creating problem specific scenario sets or by including limited recovery actions to react on the revealed scenario. The broadest of the latter concepts is developed in the B15-ARRIVAL cooperation, namely, recoverable robustness. A solution is recoverable robust, if it can be recovered by limited effort in all scenarios of a restricted scenario set. This concept allows to address applications like timetabling or platforming for which robust models were hitherto not available.
Recoverable robustness poses a number of new mathematical problems. The main goal of this project is the development and investigation of different recoverable robust models with integer and combinatorial recovery and the application of recoverable robustness in telecommunication and railway optimization.
1. Combinatorial and Integer Recovery:
The key to compact, recoverable robust models is to understand the interplay of the recovery and the restrictions to the scenario space. For most settings where the recovery is a combinatorial optimization problem (combinatorial recovery) or a linear integer program (integer recovery) this is not understood. We will thus focus on the following questions:
- How can we define recoverable robust combinatorial/integer optimization problems motivated by observations from practical applications?
- What kind of changes in respect to complexity can we observed compared to robust models?
- How can we use special structures of the recoverable robust models to develop exact algorithms or approximations?
2. Transfer to applications:
The concept of recoverable robustness is a remedy for the shortcomings of state of the art robustness in practical applications. In cooperation with researchers in the fields of telecommunication, railway optimization and logistics we will analyze the following questions:
- How can we develop problem specific scenario sets and recovery actions? How can we exploit and measure coincidental covering of these scenario sets?
- Which mathematical methods are suitable to solve recoverable robust problems to optimality?
- What gain in the objective can be observed by allowing limited recovery? What is the price for a complicated and computational expensive recovery compared to a simple and easy-to-implement strategy?
Recoverable robust shortest path problems
Networks 59, 181 - 189, 2012
C. Büsing, K.-S. Goetzmann, J. Matuschke
Compromised solutions in multicriteria combinatorial optimization
Technical Report 009-201, TU-Berlin, 2011
K.-S. Goetzmann, S. Stiller, C. Telha
Optimization over integers with robustness in cost and few constraints
WAOA '11, to appear
C. Büsing, A.M.C.A. Koster, M. Kutschka
Recoverable Robust Knapsacks: Gamma-Scenarios
Proceedings of INOC 2011, LNCS 6701, 583—588, 2011
Recoverable Robustness in Combinatorial Optimization
Cuvillier Verlag, 2011
C. Büsing, A.M.C.A. Koster, M. Kutschka
Recoverable robust knapsacks: the discrete scenario case
Optimization Letters 5, 379 – 392, 2011
C. Büsing and S. Stiller
Line planning, path constrained network flow and inapproximability
Networks 57, 106 – 113, 2011
C. Büsing, J. Maue
Robust algorithms for sorting railway cars
Proceedings of ESA 2010, LNCS 6346, 350-361, 2010