License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.21
URN: urn:nbn:de:0030-drops-63722
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6372/
Borndörfer, Ralf ;
Hoppmann, Heide ;
Karbstein, Marika
Separation of Cycle Inequalities for the Periodic Timetabling Problem
Abstract
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.
BibTeX - Entry
@InProceedings{borndrfer_et_al:LIPIcs:2016:6372,
author = {Ralf Bornd{\"o}rfer and Heide Hoppmann and Marika Karbstein},
title = {{Separation of Cycle Inequalities for the Periodic Timetabling Problem}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {21:1--21:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-015-6},
ISSN = {1868-8969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6372},
URN = {urn:nbn:de:0030-drops-63722},
doi = {10.4230/LIPIcs.ESA.2016.21},
annote = {Keywords: periodic timetabling, cycle inequalities, separation algorithm}
}
Keywords: |
|
periodic timetabling, cycle inequalities, separation algorithm |
Collection: |
|
24th Annual European Symposium on Algorithms (ESA 2016) |
Issue Date: |
|
2016 |
Date of publication: |
|
18.08.2016 |