PESP swMATH ID: 3261 Software Authors: Galli, Laura; Stiller, Sebastian Description: Strong formulations for the multi-module PESP and a quadratic algorithm for graphical Diophantine equation systems The Periodic Event Scheduling Problem (PESP) is the method of choice for real-world periodic timetabling in public transport. Its MIP formulation has been studied intensely for the case of uniform modules, i.e., when all events have the same period. In practice, multiple periods are equally important. Yet, the powerful methods developed for uniform modules generally fail for the multi-module case. We analyze a certain type of Diophantine equation systems closely related to the multi-module PESP. Thereby, we identify a structure, so-called sharp trees, that allows to solve the system in \(mathcal{O}(n^2)\) time if the modules form a linear lattice. Based on this we develop the machinery to solve multi-module PESPs on real-world scale. In our computational results the new MIP-formulations considerably improve the solvability of multi-module PESPs. Homepage: http://www.springerlink.com/content/e262n131j5322756/fulltext.pdf Related Software: PESPLib; LinTim Cited in: 2 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Strong formulations for the multi-module PESP and a quadratic algorithm for graphical Diophantine equation systems. Zbl 1287.90038Galli, Laura; Stiller, Sebastian 2010 Cited by 4 Authors 1 Galli, Laura 1 Goerigk, Marc 1 Siebert, Michael 1 Stiller, Sebastian Cited in 1 Serial 1 Computers & Operations Research Cited in 2 Fields 2 Operations research, mathematical programming (90-XX) 1 Combinatorics (05-XX) Citations by Year