6974
eng
reportzib
0
--
2018-07-31
--
Separation of Cycle Inequalities in Periodic Timetabling
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.
1438-0064
urn:nbn:de:0297-zib-69746
https://doi.org/10.1016/j.disopt.2019.100552
accepted for publication on 2019-08-13
2019/08/13
Discrete Optimization
Ralf BorndÃ¶rfer
Niels Lindner
Heide Hoppmann
Marika Karbstein
Niels Lindner
ZIB-Report
18-16
eng
uncontrolled
Periodic timetabling
eng
uncontrolled
Cycle inequality
eng
uncontrolled
Change-cycle inequality
Mathematics of Computing
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
BorndÃ¶rfer, Ralf
MODAL-RailLab
MODAL-Gesamt
Lindner, Niels
ECMath-MI7
https://opus4.kobv.de/opus4-zib/files/6974/sepa_cycle.pdf