Mixed Integer Programming for University Timetabling

Before each semester, universities face the task of creating the semester timetable. The practical procedures in generating the semester timetable vary from institution to institution. However, the ground principles and primary data are generally the same. They need to allocate times and rooms to educational events while ensuring that the individual teachers and students get a satisfactory schedule. The particular institution might incorporate various considerations and features into the fundamental schedule. Many of these features overlap, forming the basis for a generalized University Course Timetabling problem.

This thesis presents the University Course Timetabling problem and the development of benchmarking problem formulations. Although the University Timetabling Problem has been widely studied, many problem formulations are either too vague or too detailed to be used at other universities without modifications. This thesis considers the problem formulation from the International Timetabling Competition 2019 (ITC 2019) as a generalized formulation applicable at most universities. The problem formulation includes the most common features and student sectioning. The problem of student sectioning arises when the university administration must enroll students in course events such they can fulfill the course requirements.

This thesis considers both practical and academic viewpoints on solution approaches. We model the problem using Mixed Integer Programming (MIP) techniques and show that it is hard for commercial solvers to solve the resulting models. Using graph theory, we show how to improve the model formulation and simplify the user-provided problem data. We provide lower bounds on the problem by using exact methods to solve the MIP model. These bounds can be used to evaluate heuristic methods for the benchmarking datasets. We introduce a matheuristic method based on the MIP model for the practical view of the problem.

The thesis contains the scientific papers produced during the Ph.D. study. A technical report and a peer-reviewed paper describe and compare two different MIP formulations of the University Course Timetabling problem of the ITC 2019. Another peer-reviewed paper presents the matheuristic we used to win the ITC 2019. A submitted paper describes algorithms to remove redundancies from the ITC 2019 datasets. A technical report initiates the research on cutting procedures for the ITC 2019. Finally, this thesis suggests potential future research that aims at producing better solutions for the university administration staff while also discussing exact methods.