Title: On the Split Closure of the Periodic Timetabling Polytope Show Chinese title

Title: 周期时刻表多面体的分裂闭包

Abstract: The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P $=$ NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances. Show Chinese abstract

Abstract: 周期事件调度问题（PESP）是公共交通系统周期性时刻表优化的核心数学工具。 PESP 可以用几种方式表述为混合整数线性规划问题，通常具有广义整数变量。 我们研究了这些表述的分割闭包，并证明分割不等式与最近引入的翻转不等式相同。 虽然分割不等式是一种通用的混合整数规划技术，但翻转不等式是以纯组合术语定义的，即 PESP 实例所基于的有向图中的循环和弧集合。 已知翻转不等式可以在伪多项式时间内分离。 我们证明了除非 P $=$ NP，否则这是最好的可能性，但也观察到如果定义翻转不等式的循环固定，则复杂度变为线性时间。 此外，引入混合整数兼容映射后，我们比较了不同表述的分割闭包，并证明通过细分进行重新表述或二值化不会导致更强的分割闭包。 最后，我们计算估计了基准库 PESPlib 中实例的最优性间隙可以由分割切割单独关闭多少，并为五个实例提供了更好的对偶界。