TY - CHAP A1 - Lindner, Niels A1 - Liebchen, Christian ED - Huisman, Dennis ED - Zaroliagis, Christos D. T1 - Determining all integer vertices of the PESP polytope by flipping arcs T2 - 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020) N2 - We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. We finally present better dual bounds for the smallest and largest instance of the benchmarking library PESPlib. Y1 - 2020 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2020.5 VL - 85 SP - 5:1 EP - 5:18 PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany 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 - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Determining all integer vertices of the PESP polytope by flipping arcs N2 - We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. These produce better dual bounds for the smallest and largest instance of the benchmarking library PESPlib. T3 - ZIB-Report - 20-19 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Mixed Integer Programming Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78793 SN - 1438-0064 ER - TY - THES A1 - Henning, Erin T1 - Tropical Geometry Approach to Shortest Paths with Parameterized Arc Weights - A Case Study in Public Transportation Networks N2 - In graphical representations of public transportation networks, there is often some degree of uncertainty in the arc values, due to delays or transfer times. This uncertainty can be expressed as a parameterized weight on the transfer arcs. Classical shortest path algorithms often have difficulty handling parameterized arc weights and a tropical geometry approach has been shown as a possible solution. The connection between the classical shortest path problem and tropical geometry is well establish: Tropically multiplying the n × n adjacency matrix of a graph with itself n − 1 times results in the so-called Kleene star, and is a matrix-form solution to the all-pairs shortest path problem. Michael Joswig and Benjamin Schröter showed in their paper The Tropical Geometry of Shortest Paths that the same method can be used to find the solution to the all-pairs shortest path problem even in the case of variable arc weights and they proposed an algorithm to solve the single-target shortest path problem in such a case. The solution takes the form of a polyhedral subdivision of the parameter space. As the number of variable arc weights grows, the time needed to execute an implementation of this algorithm grows exponentially. As the size of a public transportation network grows, the number of variable arc weights grows exponentially as well. However, it has been observed that in public transportation networks, there are usually only a few possible shortest routes. Geometrically, this means that there should be few polyhedra in the polyhedral subdivision. This algorithm is used on an example of a real-world public transportation network and an analysis of the polyhedral subdivision is made. Then a geometrical approach is used to analyze the impact of limiting the number of transfers, and thereby limiting the number of parameterized arcs used, as an estimation of the solution to the all-pairs shortest path problem Y1 - 2020 ER - 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 - 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 - 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 - JOUR A1 - Sahin, Guvenc A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Multi-period line planning with resource transfers JF - Transportation Research Part C: Emerging Technologies N2 - Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions. Y1 - 2020 U6 - https://doi.org/10.1016/j.trc.2020.102726 VL - 119 SP - 102726 ER - TY - JOUR A1 - Raharinirina, Alexia N. A1 - Peppert, Felix A1 - von Kleist, Max A1 - Schütte, Christof A1 - Sunkara, Vikram T1 - Inferring gene regulatory networks from single-cell RNA-seq temporal snapshot data requires higher-order moments JF - Patterns N2 - Single-cell RNA sequencing (scRNA-seq) has become ubiquitous in biology. Recently, there has been a push for using scRNA-seq snapshot data to infer the underlying gene regulatory networks (GRNs) steering cellular function. To date, this aspiration remains unrealized due to technical and computational challenges. In this work we focus on the latter, which is under-represented in the literature. We took a systemic approach by subdividing the GRN inference into three fundamental components: data pre-processing, feature extraction, and inference. We observed that the regulatory signature is captured in the statistical moments of scRNA-seq data and requires computationally intensive minimization solvers to extract it. Furthermore, current data pre-processing might not conserve these statistical moments. Although our moment-based approach is a didactic tool for understanding the different compartments of GRN inference, this line of thinking—finding computationally feasible multi-dimensional statistics of data—is imperative for designing GRN inference methods. Y1 - 2021 U6 - https://doi.org/10.1016/j.patter.2021.100332 VL - 2 IS - 9 ER -