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