A Scalable Graph-based Mixed-Integer Linear Programming Approach for the Examination Timetabling Problem

In this thesis the Examination Timetabling Problem (ETP) in the Darmstadt University of Technology (TU Darmstadt) is presented and a Mixed-Integer Linear Programming (MILP) model is proposed for it. Our model concentrates on the conflicts of students. An exam-based conflict graph in which edges represent incompatibilities between exams is used. An exact MILP approach is directly using a MIP solver to solve the model, which is usually not able to solve real instances due to the complexity. In order to achieve high-quality solutions within a short computational time, we propose a scalable approach based on decomposing the entire problem into subproblems, which can be easily handled using the exact MILP approach. This approach concentrates on dealing with the conflicts. The decomposition of the problem then corresponds to the decomposition of the conflict graph. For the test instances in this thesis, the scalable approach considerably improves the solutions even in shorter time, compared with the exact MILP approach.