Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 7 von 7
Zurück zur Trefferliste

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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.