Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Separation of Cycle Inequalities for the Periodic Timetabling Problem

  • Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.
Metadaten
Author:Ralf BorndörferORCiD, Heide Hoppmann, Marika Karbstein
Document Type:In Proceedings
Parent Title (English):24th Annual European Symposium on Algorithms (ESA 2016)
Volume:57
Series:Leibniz International Proceedings in Informatics (LIPIcs)
Year of first publication:2016
DOI:https://doi.org/10.4230/LIPIcs.ESA.2016.21
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.