Projects per year
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 language | English |
---|
Publisher | Technical University of Denmark |
---|---|
Number of pages | 19 |
DOIs | |
Publication status | Published - 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.Projects
- 1 Finished
-
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/2019 → 30/09/2022
Project: PhD
Datasets
-
ITC 2019 Reduced datasets
Holm, D. S. (Creator), Technical University of Denmark, 31 Jan 2022
DOI: 10.11583/DTU.20014070, https://figshare.com/s/576e72128479df0a0fbe
Dataset