Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, November 24, 2007

Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

Rolf H. Möhring - Technische Universitšt Berlin

Timetabling and Robustness
Computing Good and Delay-Resistant Timetables

This lecture will present an overview of the theoretical background and the available algorithmic tools for computing good and delay resistant periodic timetables.
The main model is the periodic event scheduling problem (PESP) introduced by Serafini and Ukovich, which interprets periodic timetables as periodic potentials of a digraph. This model contains graph coloring as a special case, which illustrates the computational difficulty of periodic timetabling. Periodic potentials are closely related to the cycle space of the underlying graph, and finding a "short" integral basis of this space is one of the most important techniques for reducing the feasibility domain and finding good solutions.
Computing delay resistant requires a combination of the PESP model with techniques for robust optimization. As classical models of robustness (Bertsimas, Sim, Ben-Tal) are not suited for the PESP, we have developed a more general model of recoverable robustness that extends the classical concept of robust optimization and overcomes its inherent problem of being over-conservative. We will discuss this new model and demonstrate its scope on the PESP and other optimization problems.

Colloquium - 16:00

Christina Puhl -Technische Universität Berlin

Recoverable Robust Shortest Path Problems

Recoverable robustness is a concept to avoid over-conservatism in robust optimization by allowing a limited recovery after the full data is revealed.

We investigate two settings of recoverable robust shortest path problems. In both settings the costs of the arcs are subject to uncertainty. For the first setting, at most k arcs of the chosen path can be altered in the recovery. In the second setting, we commit ourselves to a path before the costs are fully known. Deviating from this choice in the recovery comes at extra costs. For each setting we consider three different classes of scenarios sets.

We show that both problems are NP-hard. For the second setting we give an approximation algorithm depending on the inflation factor and the so-called rental factor.

Letzte Aktualisierung: 18.11.2008