Separation of Cycle Inequalities in Periodic Timetabling
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-69746
accepted for publication
- Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algo- rithm for cycle inequalities, and we give 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.
Verfasserangaben: | Ralf BorndörferORCiD, Heide Hoppmann, Marika Karbstein, Niels LindnerORCiD |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | Change-cycle inequality; Cycle inequality; Periodic timetabling |
MSC-Klassifikation: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
CCS-Klassifikation: | G. Mathematics of Computing |
J. Computer Applications | |
Datum der Erstveröffentlichung: | 31.07.2018 |
Schriftenreihe (Bandnummer): | ZIB-Report (18-16) |
ISSN: | 1438-0064 |
Verlagspublikation: | Discrete Optimization |
DOI: | https://doi.org/https://doi.org/10.1016/j.disopt.2019.100552 |