TY - JOUR A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Lindner, Niels T1 - Separation of cycle inequalities in periodic timetabling T2 - Discrete Optimization N2 - Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem. Y1 - 2019 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7471 IS - 35 SP - 100552 ER -