A polyhedral study of the Travelling Tournament Problem

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.