University of Twente Student Theses


A polyhedral study of the Travelling Tournament Problem

Siemann, M.R. (2020) A polyhedral study of the Travelling Tournament Problem.

[img] PDF
Abstract:The Travelling Tournament Problem (TTP) is a sports scheduling problem in which the goal is to find a double round-robin tournament schedule with minimum total travel distance. Additional constraints are the no-repeaters constraint and constraints on the length of home stands and road trips. Without these constraints, the problem is called unconstrained. In this thesis, the TTP is modelled as an integer program and the polytope of solutions is investigated. The dimension of the solution polytope of the unconstrained problem is found and proved. Using this result, it is proved that a certain class of valid inequalities is facet-defining for the unconstrained problem. A separate part of this thesis is spent on analysing the equivalences between three tournament scheduling methods: the circle method, the canonical 1-factorisation and the Kirkman tournament. It is proved that the last two methods are equivalent up to permutation, a result that was missing in electronically available literature.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page