24.04.2025

Auf Einladung von Prof. Dr. Marie Schmidt findet der folgende Vortrag statt:

Donnerstag, 24. April 2025, 16:15 Uhr, Übungsraum II, Informatikgebäude, Am Hubland

Dr. Philine Schiewe
Aalto University School of Science, Systems Analysis Laboratory, Finland

Integrated optimization problems involving shortest paths

Abstract

Finding shortest paths is one of the best-known problems in combinatorial optimization. In static settings, i.e., when all edge costs in a graph are known, the problem can be solved in polynomial time. However, in many applications a chicken-and-egg problem occurs: The costs of a path depend on its usage and the usage of a path depends on its costs. We consider two different cases of these so-called integrated optimization problems. 

First, when considering generalized optimum requirement graphs, we integrate finding spanning graphs and all-pair shortest paths. Here, we can show that the problem is NP-hard already for wheel graphs and identify polynomially solvable cases exploiting symmetries. We present flow-based integer-programming formulations for the generic and symmetric variant of the problem and experimentally evaluate the structure of optimum requirement graphs on orb-webs. 

Second, we consider the problem of finding an optimal periodic timetable in public transport planning. Again, the quality of a timetable is determined by the passenger routes, i.e., shortest paths for the timetable, while the passenger routes depend on the timetable itself. We model the resulting integrated problem and present both exact and heuristic approaches for reducing the problem size. When analyzing the benefits of the integrated approach compared to the traditional sequential one, we can show that the periodicity parameter provides an upper bound on the improvement and that this bound is (almost) tight. Finally, we compare these theoretical bounds to real-world improvements by experimentally evaluating benchmark data.

URL: https://sal.aalto.fi/en/personnel/philine.schiewe/