Filtern
Erscheinungsjahr
- 2018 (1)
Dokumenttyp
- ZIB-Report (1)
Sprache
- Englisch (1) (entfernen)
Volltext vorhanden
- ja (1) (entfernen)
Gehört zur Bibliographie
- nein (1)
Schlagworte
- Cycle inequality (1) (entfernen)
Institut
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.