Separation of cycle inequalities for the periodic timetabling problem

DOI10.4230/LIPICS.ESA.2016.21MaRDI QIDQ4606290zbMATH OpenOpenAlexFDO

Authors Ralf Borndörfer, Heide Hoppmann, Marika Karbstein

Publication date 2 March 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.ESA.2016.21

zbMATH Keywords

separation algorithmperiodic timetablingcycle inequalities

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Recommendations

• Separation of cycle inequalities in periodic timetabling
• Forward and line-based cycle bases for periodic timetabling
• Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time
• Separating clique tree and bipartition inequalities in polynomial time
• Separating subdivision of bicycle wheel inequalities over cut polytopes

Cited in

(4)

• The second Chvátal closure can yield better railway timetables
• Integral cycle bases for cyclic timetabling
• Separation of cycle inequalities in periodic timetabling
• Determining all integer vertices of the PESP polytope by flipping arcs

Describes a project that uses

Uses Software

• SCIP
• CPLEX
• GAMS

This page was built for publication: Separation of cycle inequalities for the periodic timetabling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606290)