TY - GEN A1 - Lindner, Niels A1 - Reisch, Julian T1 - Parameterized Complexity of Periodic Timetabling N2 - Public transportation networks are typically operated with a periodic timetable. The Periodic Event Scheduling Problem (PESP) is the standard mathematical modelling tool for periodic timetabling. Since PESP can be solved in linear time on trees, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth. We show that deciding the feasibility of a PESP instance is NP-hard even when the treewidth is 2, the branchwidth is 2, or the carvingwidth is 3. Analogous results hold for the optimization of reduced PESP instances, where the feasibility problem is trivial. To complete the picture, we present two pseudo-polynomial-time dynamic programming algorithms solving PESP on input networks with bounded tree- or branchwidth. We further analyze the parameterized complexity of PESP with bounded cyclomatic number, diameter, or vertex cover number. For event-activity networks with a special -- but standard -- structure, we give explicit and sharp bounds on the branchwidth in terms of the maximum degree and the carvingwidth of an underlying line network. Finally, we investigate several parameters on the smallest instance of the benchmarking library PESPlib. T3 - ZIB-Report - 20-15 KW - Parameterized complexity KW - Periodic timetabling KW - Treewidth KW - Branchwidth KW - Carvingwidth KW - Periodic Event Scheduling Problem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78314 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Masing, Berenike T1 - On the Split Closure of the Periodic Timetabling Polytope N2 - The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P $=$ NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances. T3 - ZIB-Report - 23-16 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Split Closure KW - Mixed-Integer Programming Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91156 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Timetable Merging for the Periodic Event Scheduling Problem N2 - We propose a new mixed integer programming based heuristic for computing new benchmark primal solutions for instances of the PESPlib. The PESPlib is a collection of instances for the Periodic Event Scheduling Problem (PESP), comprising periodic timetabling problems inspired by real-world railway timetabling settings, and attracting several international research teams during the last years. We describe two strategies to merge a set of good periodic timetables. These make use of the instance structure and minimum weight cycle bases, finally leading to restricted mixed integer programming formulations with tighter variable bounds. Implementing this timetable merging approach in a concurrent solver, we improve the objective values of the best known solutions for the smallest and largest PESPlib instances by 1.7 and 4.3 percent, respectively. T3 - ZIB-Report - 21-06 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Railway Timetabling KW - PESPlib KW - Benchmark Solutions KW - Mixed Integer Programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81587 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - van Lieshout, Rolf T1 - Benders Decomposition for the Periodic Event Scheduling Problem N2 - The Periodic Event Scheduling Problem (PESP) is the central mathematical model behind the optimization of periodic timetables in public transport. We apply Benders decomposition to the incidence-based MIP formulation of PESP. The resulting formulation exhibits particularly nice features: The subproblem is a minimum cost network flow problem, and feasibility cuts are equivalent to the well-known cycle inequalities by Odijk. We integrate the Benders approach into a branch-and-cut framework, and assess the performance of this method on instances derived from the benchmarking library PESPlib. T3 - ZIB-Report - 21-29 KW - Periodic Timetabling KW - Periodic Event Scheduling Problem KW - Benders Decomposition KW - Mixed-Integer Programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-83338 SN - 1438-0064 ER -