• search hit 12 of 23
Back to Result List

Determining All Integer Vertices of the PESP Polytope by Flipping Arcs

  • 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.

Download full text files

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author:Niels LindnerORCiD, Christian LiebchenORCiDGND
URN:urn:nbn:de:kobv:526-opus4-13650
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2020.5
ISBN:978-3-95977-170-2
ISSN:2190-6807
Parent Title (English):20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Publisher:Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Place of publication:Dagstuhl, Germany
Editor:Dennis Huisman, Christos D. Zaroliagis
Document Type:Conference Proceeding
Language:English
Year of Publication:2020
Publishing Institution:Technische Hochschule Wildau
Release Date:2021/01/08
Source:Lindner, N., & Liebchen, C. (2020). Determining All Integer Vertices of the PESP Polytope by Flipping Arcs In Dennis Huisman and Christos D. Zaroliagis, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020) (pp. 5:1-5:18). Saarbrücken/Wadern,Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing (OASIcs – OpenAccess Series in Informatics).
Faculties an central facilities:Fachbereich Ingenieur- und Naturwissenschaften
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 005 Computerprogrammierung, Programme, Daten
Licence (German):Creative Commons - CC BY 3.0 - Namensnennung 3.0 Unported
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.