A Cutting Plane Algorithm for the International Timetabling Competition 2019 Problem

Research output: Book/ReportReport

19 Downloads (Pure)

Abstract

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.
Original languageEnglish
Number of pages25
Publication statusPublished - 2022

Keywords

  • Mixed Integer Programming
  • Cutting plane
  • University Course Timetabling
  • International Timetabling Competition 2019
  • ITC 2019

Fingerprint

Dive into the research topics of 'A Cutting Plane Algorithm for the International Timetabling Competition 2019 Problem'. Together they form a unique fingerprint.
  • Aarhus University

    Dennis Søren Holm (Visiting researcher) & Jens Lysgaard (Visiting researcher)

    7 Dec 202027 Apr 2021

    Activity: Visiting an external institutionVisiting another research institution

Cite this