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)

Abstract

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
Volume25
Pages (from-to)429–452
ISSN1094-6136
DOIs
Publication statusPublished - 2022

Keywords

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

Fingerprint

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.

    01/02/201930/09/2022

    Project: PhD

  • DSUM Presentation

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

    2 Sept 2020

    Activity: Talks and presentationsConference presentations

    File

Cite this