Strong formulations for the Multi-module PESP and a quadratic algorithm for Graphical Diophantine Equation Systems

dc.contributor.authorGalli, Laura
dc.contributor.authorStiller, Sebastian
dc.description.abstractThe 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 modules are equally important. The strength of current methods for uniform modules rests on three ingredients: Every feasible instance allows for an optimal solution with a certain structure. Therefore, it can be reformulated with the use of an integral cycle basis. Finally, a certain type of rounding cuts arising from cycles has proven very powerful. All of this fails in the multi-module case. Therefore, applications with multiple periods were hardly solvable so far. 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 O (n^2) time. We show, a sharp tree is guaranteed to exist and found by a similar algorithm, if the modules form a linear lattice. Based on this we develop the machinery to solve multi-module PESPs on real-world scale. In particular, we recover all three ingredients for the multi-module case. In our computational results the new MIP-formulations drastically improve the solvability of multi-module PESPs. We also demonstrate that without sharp trees no similar approach can be hoped for.en
dc.subject.ddc510 Mathematiken
dc.subject.otherinteger programmingen
dc.subject.otherperiodic event schedulingen
dc.subject.otherdiophantine equation systemsen
dc.subject.otherpublic transporten
dc.titleStrong formulations for the Multi-module PESP and a quadratic algorithm for Graphical Diophantine Equation Systemsen
dc.typeResearch Paperen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2010, 09en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
119.87 KB
Adobe Portable Document Format