期刊
JOURNAL OF SCHEDULING
卷 25, 期 4, 页码 405-428出版社
SPRINGER
DOI: 10.1007/s10951-022-00724-y
关键词
Mixed integer programming; Conflict graph; Clique cover; University timetabling; International Timetabling Competition 2019; ITC 2019
资金
- MaCom A/S
- Innovation Fund Denmark (IFD)
- IFD
This paper introduces a graph-based mixed integer programming (MIP) formulation for solving university timetabling problem, and proposes a reduction algorithm to optimize the input data. The results show that the algorithm outperforms existing MIP formulations and becomes the state-of-the-art solution for ITC 2019. Additionally, the paper discusses other approaches to strengthen the MIP.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据