TY - GEN A1 - Liebchen, Christian T1 - Finding Short Integral Cycle Bases for Cyclic Timetabling N2 - Cyclic timetabling for public transportation companies is usually modeled by the periodic event scheduling problem. To deduce a mixed-integer programming formulation, artificial integer variables have to be introduced. There are many ways to define these integer variables. We show that the minimal number of integer variables required to encode an instance is achieved by introducing an integer variable for each element of some integral cycle basis. An integral cycle basis consists of |A|-|V|+1 oriented cycles of a directed graph D = (V;A) that enable any oriented cycle of the directed graph to be expressed as an integer linear combination. The solution times for the originating application vary extremely with different integral cycle bases. However, our computational studies show that the width of integral cycle bases is a good empirical measure for the solution time of the MIP. Clearly, integral cycle bases permit a much wider choice than the former standard approach, in which integer variables are associated with the co-tree arcs of some spanning tree. Hence, to formulate better solvable integer programs, we present algorithms that construct integral cycle bases of small width. To that end, we investigate classes of directed cycle bases that are closely related to integral cycle bases, namely (generalized) fundamental and undirected cycle bases. This gives rise to both, a compact classification of directed cycle bases and notable reductions of running times for cyclic timetabling. Y1 - 2003 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/22 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-225 ER -