Separation of cycle inequalities in periodic timetabling
- 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.
Additional Services
| Author: | Ralf BorndörferORCiD, Heide Hoppmann, Marika Karbstein, Niels LindnerORCiD |
|---|---|
| Document Type: | Article |
| Parent Title (English): | Discrete Optimization |
| Issue: | 35 |
| First Page: | 100552 |
| Year of first publication: | 2020 |
| Preprint: | urn:nbn:de:0297-zib-69746 |
| DOI: | https://doi.org/10.1016/j.disopt.2019.100552 |
