Separation of cycle inequalities for the periodic timetabling problem

DOI10.4230/LIPICS.ESA.2016.21zbMATH Open1397.90169OpenAlexW2530585403MaRDI QIDQ4606290FDOQ4606290

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

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

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)

Cited In (4)

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

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)