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

Dennis S. Holm, Rasmus Ø. Mikkelsen (), Matias Sørensen and Thomas J. R. Stidsen ()
Additional contact information
Dennis S. Holm: Technical University of Denmark
Rasmus Ø. Mikkelsen: Technical University of Denmark
Thomas J. R. Stidsen: Technical University of Denmark

Journal of Scheduling, 2022, vol. 25, issue 4, No 3, 405-428

Abstract: 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.

Keywords: Mixed integer programming; Conflict graph; Clique cover; University timetabling; International Timetabling Competition 2019; ITC 2019 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00724-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:25:y:2022:i:4:d:10.1007_s10951-022-00724-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00724-y

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().