TY - JOUR A1 - Lindner, Niels A1 - Reisch, Julian T1 - An analysis of the parameterized complexity of periodic timetabling JF - Journal of Scheduling N2 - Public transportation networks are typically operated with a periodic timetable. The periodic event scheduling problem (PESP) is the standard mathematical modeling tool for periodic timetabling. PESP is a computationally very challenging problem: For example, solving the instances of the benchmarking library PESPlib to optimality seems out of reach. Since PESP can be solved in linear time on trees, and the treewidth is a rather small graph parameter in the networks of the PESPlib, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth, or even better, fixed-parameter tractable algorithms. 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. Moreover, we show W[1]-hardness of the general feasibility problem with respect to treewidth, which means that we can most likely only accomplish pseudo-polynomial-time algorithms on input networks with bounded tree- or branchwidth. We present two such algorithms based on dynamic programming. 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. Y1 - 2022 U6 - https://doi.org/10.1007/s10951-021-00719-1 VL - 25 SP - 157 EP - 176 ER - TY - CHAP A1 - Masing, Berenike A1 - Lindner, Niels A1 - Borndörfer, Ralf ED - Trautmann, Norbert ED - Drägi, Mario T1 - Optimal Line Plans in the Parametric City and the Impact of In-Motion Costs T2 - Operations Research Proceedings 2021 N2 - Line planning in public transport involves determining vehicle routes and assigning frequencies of service such that travel demands are satisfied. We evaluate how line plans, which are optimal with respect to in-motion costs (IMC), the objective function depending purely on arc-lengths for both user and operator costs, performs with respect to the value of resources consumed (VRC). The latter is an elaborate, socio-economic cost function which includes discomfort caused by delay, boarding and alighting times, and transfers. Even though discomfort is a large contributing factor to VRC and is entirely disregarded in IMC,  we observe that the two cost functions are qualitatively comparable. Y1 - 2022 SN - 978-3-031-08623-6 U6 - https://doi.org/10.1007/978-3-031-08623-6_44 SP - 295 EP - 301 PB - Springer, Cham ER - TY - JOUR A1 - Schiewe, Philine A1 - Goerigk, Marc A1 - Lindner, Niels T1 - Introducing TimPassLib – A Library for Integrated Periodic Timetabling and Passenger Routing JF - Operations Research Forum N2 - Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing. Y1 - 2023 U6 - https://doi.org/10.1007/s43069-023-00244-1 VL - 4 IS - 3 SP - 64 ER - TY - JOUR A1 - Masing, Berenike A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - The price of symmetric line plans in the Parametric City JF - Transportation Research Part B: Methodological N2 - We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. We prove that the symmetry gap is small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations. Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88613 VL - 166 SP - 419 EP - 443 ER - TY - CHAP A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling T2 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [Borndörfer et al., 2020]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [Bortoletto et al., 2022]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances. Y1 - 2022 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022.3 VL - 106 SP - 3:1 EP - 3:19 ER - TY - CHAP A1 - Bortoletto, Enrico A1 - Lindner, Niels A1 - Masing, Berenike T1 - Periodic Timetabling with Cyclic Order Constraints T2 - 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) N2 - Periodic timetabling for highly utilized railway networks is a demanding challenge. We formulate an infrastructure-aware extension of the Periodic Event Scheduling Problem (PESP) by requiring that not only events, but also activities using the same infrastructure must be separated by a minimum headway time. This extended problem can be modeled as a mixed-integer program by adding constraints on the sum of periodic tensions along certain cycles, so that it shares some structural properties with standard PESP. We further refine this problem by fixing cyclic orders at each infrastructure element. Although the computational complexity remains unchanged, the mixed-integer programming model then becomes much smaller. Furthermore, we also discuss how to find a minimal subset of infrastructure elements whose cyclic order already prescribes the order for the remaining parts of the network, and how cyclic order information can be modeled in a mixed-integer programming context. In practice, we evaluate the impact of cyclic orders on a real-world instance on the S-Bahn Berlin network, which turns out to be computationally fruitful. Y1 - 2023 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2023.7 VL - 115 SP - 7:1 EP - 7:18 ER - TY - CHAP A1 - Masing, Berenike A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice T2 - 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) N2 - We consider maintenance sites for urban rail systems, where unavailable tracks typically require changes to the regular timetable, and often even to the line plan. In this paper, we present an integrated mixed-integer linear optimization model to compute an optimal line plan that makes best use of the available tracks, together with a periodic timetable, including its detailed routing on the tracks within the stations. The key component is a flexible, turn-sensitive event-activity network that allows to integrate line planning and train routing using a track choice extension of the Periodic Event Scheduling Problem (PESP). Major goals are to maintain as much of the regular service as possible, and to keep the necessary changes rather local. Moreover, we present computational results on real construction site scenarios on the S-Bahn Berlin network. We demonstrate that this integrated problem is indeed solvable on practically relevant instances. Y1 - 2023 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2023.5 VL - 115 SP - 5:1 EP - 5:15 ER - TY - CHAP A1 - Lindner, Niels A1 - van Lieshout, Rolf T1 - Benders Decomposition for the Periodic Event Scheduling Problem T2 - Operations Research Proceedings 2021 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. Y1 - 2022 U6 - https://doi.org/10.1007/978-3-031-08623-6_43 SP - 289 EP - 294 PB - Springer International Publishing CY - Cham ER - TY - CHAP A1 - Löbel, Fabian A1 - Lindner, Niels A1 - Borndörfer, Ralf ED - Neufeld, Janis S. ED - Buscher, Udo ED - Lasch, Rainer ED - Möst, Dominik ED - Schönberger, Jörn T1 - The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing T2 - Operations Research Proceedings 2019 N2 - The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances. Y1 - 2020 SN - 978-3-030-48438-5 U6 - https://doi.org/https://doi.org/10.1007/978-3-030-48439-2_92 SP - 757 EP - 763 PB - Springer International Publishing CY - Cham ER - TY - JOUR A1 - Masing, Berenike A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Periodic timetabling with integrated track choice for railway construction sites JF - Journal of Rail Transport Planning & Management N2 - We propose a mixed-integer linear programming model to generate and optimize periodic timetables with integrated track choice in the context of railway construction sites. When a section of a railway network becomes unavailable, the nearby areas are typically operated close to their capacity limits, and hence carefully modeling headways and allowing flexible routings becomes vital. We therefore discuss first how to integrate headway constraints into the Periodic Event Scheduling Problem (PESP) that do not only prevent overtaking, but also guarantee conflict-free timetables in general and particularly inside stations. Secondly, we introduce a turn-sensitive event-activity network, which is able to integrate routing alternatives for turnarounds at stations, e.g., turning at a platform vs. at a pocket track for metro-like systems. We propose several model formulations to include track choice, and finally evaluate them on six real construction site scenarios on the S-Bahn Berlin network. Y1 - 2023 U6 - https://doi.org/10.1016/j.jrtpm.2023.100416 VL - 28 SP - 100416 ER - TY - CHAP A1 - Şahin, Güvenç A1 - Lindner, Niels A1 - Schlechte, Thomas ED - Pardalos, P. M. ED - Prokopyev, O. A. T1 - Line Planning Problem T2 - Encyclopedia of Optimization Y1 - 2023 SN - 978-3-030-54621-2 U6 - https://doi.org/10.1007/978-3-030-54621-2_782-1 SP - 1 EP - 6 PB - Springer International Publishing CY - Cham ER - TY - GEN A1 - Masing, Berenike A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - The Price of Symmetric Line Plans in the Parametric City N2 - We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. The symmetry gap is provably small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations. T3 - ZIB-Report - 22-01 KW - line planning KW - mixed integer programming KW - parametric city modeling Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85648 SN - 1438-0064 ER - TY - JOUR A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Timetable merging for the Periodic Event Scheduling Problem JF - EURO Journal on Transportation and Logistics 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. Y1 - 2022 U6 - https://doi.org/10.1016/j.ejtl.2022.100081 VL - 11 SP - 100081 ER - TY - GEN A1 - Masing, Berenike A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - Optimal Line Plans in the Parametric City and the Impact of In-Motion Costs N2 - Line planning in public transport involves determining vehicle routes and assigning frequencies of service such that travel demands are satisfied. We evaluate how line plans, which are optimal with respect to in-motion costs (IMC), the objective function depending purely on arc-lengths for both user and operator costs, performs with respect to the value of resources consumed (VRC). The latter is an elaborate, socio-economic cost function which includes discomfort caused by delay, boarding and alighting times, and transfers. Even though discomfort is a large contributing factor to VRC and is entirely disregarded in IMC, we observe that the two cost functions are qualitatively comparable. T3 - ZIB-Report - 21-27 KW - line planning KW - public transport KW - mixed-integer prgramming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-84195 SN - 1438-0064 ER - TY - JOUR A1 - Lindner, Niels T1 - Hypersurfaces with defect JF - Journal of Algebra N2 - A projective hypersurface X⊆P^n has defect if h^i(X) ≠ h^i(P^n) for some i∈{n,…,2n−2} in a suitable cohomology theory. This occurs for example when X⊆P^4 is not Q-factorial. We show that hypersurfaces with defect tend to be very singular: In characteristic 0, we present a lower bound on the Tjurina number, where X is allowed to have arbitrary isolated singularities. For X with mild singularities, we prove a similar result in positive characteristic. As an application, we obtain an estimate on the asymptotic density of hypersurfaces without defect over a finite field. Y1 - 2020 U6 - https://doi.org/10.1016/j.jalgebra.2020.02.022 VL - 555 SP - 1 EP - 35 ER - TY - CHAP A1 - Bortoletto, Enrico A1 - Lindner, Niels ED - Voigt, Guido ED - Fliedner, Malte ED - Haase, Knut ED - Brüggemann, Wolfgang ED - Hoberg, Kai ED - Meissner, Jörn T1 - Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times T2 - Operations Research Proceedings 2023 N2 - The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice. Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-58405-3_51 SP - 397 EP - 402 ER - TY - CHAP A1 - Ebert, Patricia A1 - Masing, Berenike A1 - Lindner, Niels A1 - Gleixner, Ambros T1 - Sorting Criteria for Line-based Periodic Timetabling Heuristics T2 - Operations Research Proceedings 2024. OR 2024 N2 - It is well-known that optimal solutions are notoriously hard to find for the Periodic Event Scheduling Problem (PESP), which is the standard mathematical formulation to optimize periodic timetables in public transport. We consider a class of incremental heuristics that have been demonstrated to be effective by Lindner and Liebchen (2023), however, for only one fixed sorting strategy of lines along which a solution is constructed. Thus, in this paper, we examine a variety of sortings based on the number, weight, weighted span, and lower bound of arcs, and test for each setting various combinations of the driving, dwelling, and transfer arcs of lines. Additionally, we assess the impact on the incremental extension of the event-activity network by minimizing resp. maximizing a connectivity measure between subsets of lines. We compare our 27 sortings on the railway instances of the benchmarking library PESPlib within the ConcurrentPESP solver framework. We are able to find five new incumbent solutions, resulting in improvements of up to 2%. Y1 - 2025 SP - 348 EP - 354 ER - TY - CHAP A1 - Pedersen, Jaap A1 - Lindner, Niels A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Comparing Branching Rules for the Quota Steiner Tree Problem with Interference T2 - Operations Research Proceedings 2025 N2 - Branching decisions play a crucial role in branch-and-bound algorithms for solving combinatorial optimization problems. In this paper, we investigate several branching rules applied to the Quota Steiner Tree Problem with Interference (QSTPI). The Quota Steiner Tree Problem (QSTP) generalizes the classical Steiner Tree Problem (STP) in graphs by seeking a minimum-cost tree that connects a subset of profit-associated vertices whose cumulative profit meets or exceeds a given quota. The QSTPI introduces interference among vertices: Selecting certain vertices simultaneously reduces their individual contributions to the overall profit. This problem arises, for example, in positioning and connecting wind turbines, where turbines possibly shadow other turbines, reducing their energy yield. Unlike classical STP variants, large QSTPI instances require significantly more branching to compute provably optimal solutions. In contrast to branching on variables, we utilize the combinatorial structure of the QSTPI by branching on the graph's vertices. We adapt classical and problem-specific branching rules and present a comprehensive computational study comparing the effectiveness of these branching strategies. Y1 - 2026 ER - TY - CHAP A1 - Koch, Thorsten A1 - Kempke, Nils-Christian A1 - Lindner, Niels A1 - Mehl, Lukas A1 - Wetzel, Manuel A1 - Zittel, Janina T1 - High-Performance Robust Energy System Planning with Storage: A Single-LP Approach T2 - Proceedings of URBSENSE 2026 - 1st International Workshop on URBan SENSEmaking and Intelligence for Safer Cities Y1 - 2026 ER - TY - CHAP A1 - Riccardi, Gabor A1 - Lindner, Niels T1 - On The Minimum-Weight Forward (Weakly) Fundamental Cycle Basis Problem in Directed Graphs T2 - International Network Optimization Conference 2026 (INOC 2026) N2 - The cycle space of a directed graph is generated by a cycle basis, where, in general, cycles are allowed to have both forward and backward arcs. In a forward cycle, all arcs have to follow the given direction. We study the existence, structure, and computational complexity of minimum-weight forward cycle bases in directed graphs. We give a complete structural characterization of digraphs that admit weakly fundamental (and hence integral) forward cycle bases, showing that this holds if and only if every block is either strongly connected or a single arc. We further provide an easily verifiable characterization of when a strongly connected digraph admits a forward fundamental cycle basis, proving that such a basis exists if and only if the set of directed cycles has cardinality equal to the cycle rank; in this case, the basis is unique and computable in polynomial time, and nonexistence can likewise be certified efficiently. Lastly, we show that while minimum-weight forward fundamental cycle bases can be found in polynomial time whenever they exist, the minimum-weight forward weakly fundamental cycle basis problem is NP-hard via a polynomial-time reduction from the minimum-weight weakly fundamental cycle basis problem on digraphs with metric weights. Y1 - 2026 ER -