A parallelized matheuristic for the International Timetabling Competition 2019

Rasmus Mikkelsen*, Dennis S. Holm

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

80 Downloads (Pure)


The International Timetabling Competition 2019 (ITC 2019) presents a novel and generalized university timetabling problem composed of traditional class time and room assignment and student sectioning. In this paper, we present a parallelized matheuristic tailored to the ITC 2019 problem. The matheuristic is composed of multiple methods using the graph-based mixed-integer programming (MIP) model defined for the ITC 2019 problem by Holm et al. (A graph-based MIP formulation of the International Timetabling Competition 2019. J Sched, 2022. https://doi.org/10.1007/s10951-022-00724-y). We detail all methods included in the parallelized matheuristic and the collaboration between them. The parallelized matheuristic includes two methods for producing initial solutions and uses a fix-and-optimize matheuristic to improve solutions. Additionally, the method uses the full MIP model to calculate lower bounds. We describe how the methods perform collaboratively through solution sharing, and a diversification scheme invoked when the search stagnates. Furthermore, we explain how we decompose the problem for instances with a large number of students. We evaluate components of the parallelized matheuristic using the 30 benchmark instances of the ITC 2019. The complete parallelized matheuristic performs well, even solving some instances to proven optimality. The presented method is the winning algorithm of the competition, further demonstrating its quality.

Original languageEnglish
JournalJournal of Scheduling
Pages (from-to)429–452
Publication statusPublished - 2022


  • Fix-and-optimize
  • International Timetabling Competition 2019
  • ITC 2019
  • Mixed-integer programming
  • Parallelized matheuristic
  • University timetabling


Dive into the research topics of 'A parallelized matheuristic for 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.


    Project: PhD

  • DSUM Presentation

    Dennis Søren Holm (Invited speaker) & Rasmus Ørnstrup Mikkelsen (Invited speaker)

    2 Sept 2020

    Activity: Talks and presentationsConference presentations


Cite this