English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Periodic Event Scheduling Problem (PESP) is the central mathematical toolfor periodic timetable optimization in public transport. PESP can be formulatedin several ways as a mixed-integer linear program with typically generalinteger variables. We investigate the split closure of these formulations andshow that split inequalities are identical with the recently introduced flipinequalities. While split inequalities are a general mixed-integer programmingtechnique, flip inequalities are defined in purely combinatorial terms, namelycycles and arc sets of the digraph underlying the PESP instance. It is knownthat flip inequalities can be separated in pseudo-polynomial time. We provethat this is best possible unless P $=$ NP, but also observe that thecomplexity becomes linear-time if the cycle defining the flip inequality isfixed. Moreover, introducing mixed-integer-compatible maps, we compare thesplit closures of different formulations, and show that reformulation orbinarization by subdivision do not lead to stronger split closures. Finally, weestimate computationally how much of the optimality gap of the instances of thebenchmark library PESPlib can be closed exclusively by split cuts, and providebetter dual bounds for five instances.

On the Split Closure of the Periodic Timetabling Polytope