@misc{LindnerLiebchen, author = {Lindner, Niels and Liebchen, Christian}, title = {Determining all integer vertices of the PESP polytope by flipping arcs}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2020.5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78793}, abstract = {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.}, language = {en} } @misc{LindnerLiebchenMasing, author = {Lindner, Niels and Liebchen, Christian and Masing, Berenike}, title = {Forward Cycle Bases and Periodic Timetabling}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2021.2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82756}, abstract = {Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance \texttt{R1L1} of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.}, language = {en} } @misc{LindnerLiebchen, author = {Lindner, Niels and Liebchen, Christian}, title = {Timetable Merging for the Periodic Event Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81587}, abstract = {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.}, language = {en} } @misc{BorndoerferLindnerRoth, author = {Bornd{\"o}rfer, Ralf and Lindner, Niels and Roth, Sarah}, title = {A Concurrent Approach to the Periodic Event Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71907}, abstract = {We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.}, language = {en} }