Monday, November 24, 2007
Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
Lecture - 14:15
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
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.