Project B23

Robust Optimization for Network Applications

DFG Research Center Matheon Technische Universität Berlin
Duration: June 2010 - May 2014
Project heads: Rolf H. Möhring
Sebastian Stiller
Researcher: Christina Büsing
Support: DFG Research Center "Mathematics for Key Technologies" (Matheon)

Project description.


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.

Research program

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?


[1] Ch. Büsing and J. Maue.
Robust Algorithms for Sorting Railway Cars.
Proceedings of ESA 2010.
[2] Ch. Büsing, A. M. C. A. Koster and M. Kutschka.
Recoverable Robust Knapsacks: The Discrete Scenario Case.
To appear in Optimization Letters 2011


Within Matheon: