Data Reductions for the International Timetabling Competition 2019 Problem

Dennis Søren Holm*

*Corresponding author for this work

Research output: Book/ReportReportResearchpeer-review

150 Downloads (Pure)

Abstract

When solving real-world optimization problems with large datasets, we often encounter redundancies. The data may originate from different systems or employees, leading to a loss of overview. Some structures may not individually cause redundancy, but the combination will. It is also the case for the International Timetabling Competition 2019 (ITC 2019) problem. The ITC 2019 considers a generalized formulation of the university course timetabling problem, where data are collected from 10 institutions on five continents. An example of redundancy is that a class’s available times contain infeasible entries because constraints disallow the time assignment. The employee entering the valid class times may not know the limitations or have the necessary overview of the whole dataset to make such a derivation. This paper shows an algorithm to reduce the available times and rooms for classes in the ITC 2019 data. The paper introduces methods from graph theory to efficiently reduce the number of decision variables. These methods are applicable for other problems formulated as Binary/Integer Programs. Furthermore, specifically for the ITC 2019 problem, the algorithm removes redundant distribution constraints.
Original languageEnglish
PublisherTechnical University of Denmark
Number of pages19
DOIs
Publication statusPublished - 2022

Keywords

  • Integer Programming
  • Conflict graph
  • Data reduction
  • International Timetabling Competition 2019
  • ITC 2019

Fingerprint

Dive into the research topics of 'Data Reductions for the International Timetabling Competition 2019 Problem'. Together they form a unique fingerprint.
  • Strategic University Timetabling

    Holm, D. S. (PhD Student), Pisinger, D. (Examiner), Stidsen, T. J. R. (Main Supervisor), Christiansen, L. E. (Supervisor), Müller, T. (Examiner) & Sørensen, M. (Supervisor)

    01/02/201930/09/2022

    Project: PhD

Cite this