A graph-based MIP formulation of the International Timetabling Competition 2019

Dennis S. Holm, Rasmus Mikkelsen, Matias Sørensen, Thomas J.R. Stidsen

Research output: Contribution to journalJournal articleResearchpeer-review

205 Downloads (Pure)

Abstract

The International Timetabling Competition 2019 (ITC 2019) posed a university timetabling problem involving assigning classes to times and rooms for an entire semester while assigning students to required classes. We propose a new mixed integer programming (MIP) formulation of the problem. The MIP formulation takes advantage of different graph structures in conflict graphs to construct a strong formulation of the constraints. In addition, we introduce a reduction algorithm that removes redundancies from the input data. We show that the reduction algorithm, combined with the graph-based MIP formulation, outperforms the MIP formulated by Holm et al. (A MIP formulation of the International Timetabling Competition 2019 problem, 2020) and thus becomes the new state-of-the-art MIP formulation for the ITC 2019. This paper reports the graph-based MIP formulation, which we used during the ITC 2019, and discusses additional approaches that one can use to strengthen the MIP.
Original languageEnglish
JournalJournal of Scheduling
Volume25
Pages (from-to)405–428
Number of pages24
ISSN1094-6136
DOIs
Publication statusPublished - 2022

Keywords

  • Mixed integer programming
  • Conflict graph
  • Clique cover
  • University timetabling
  • International Timetabling Competition 2019
  • ITC 2019

Fingerprint

Dive into the research topics of 'A graph-based MIP formulation of the International Timetabling Competition 2019'. Together they form a unique fingerprint.
  • Strategic University Timetabling

    Holm, D. S., Pisinger, D., Stidsen, T. J. R., Christiansen, L. E., Sørensen, M. & Müller, T.

    01/02/201930/09/2022

    Project: PhD

Cite this