A Cutting Plane Algorithm for the International Timetabling Competition 2019 Problem

The International Timetabling Competition 2019 (ITC 2019) considers a university course timetabling problem where semester events must be assigned a time and a room while students must be enrolled in classes according to their course registration. Holm et al. (2022) show a graph-based Mixed Integer Programming (MIP) formulation of the ITC 2019 problem.

The MIP model uses various graph structures to givea strong formulation. However, the MIP model is still hard to solve for many of the 30 ITC 2019 instances. To generate high-quality solutions, Mikkelsen and Holm (2022) use a parallelized fix-and-optimize matheuristic based on the graph-based MIP model.

The matheuristic found the best solutions to 29 of 30 ITC 2019 instances during the competition and was the winning algorithm. Even though the algorithm won the competition superiorly, only five instances are solved to optimality. This technical report aims to research the possibilities of having an exact method for solving the ITC 2019 instances.

We do this by investigating the Linear Programming (LP) relaxation of the graph-based MIP model and introducing groups of constraints that might be beneficial to use as cuts. This report will focus on solving the LP relaxation with an iterative cutting plane algorithm. The search for a usable cutting plane algorithm provides two new lower bounds on the ITC 2019 instances.