Tianyi Liu
A Scalable Graph-based Mixed-Integer Linear Programming Approach for the Examination Timetabling Problem.
Rel. Roberto Tadei. Politecnico di Torino, Master of science program in Communications And Computer Networks Engineering, 2018
|
Preview |
PDF (Tesi_di_laurea)
- Thesis
Licence: Creative Commons Attribution Non-commercial No Derivatives. Download (1MB) | Preview |
Abstract
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
Relators
Academic year
Publication type
Number of Pages
Course of studies
Classe di laurea
Ente in cotutela
URI
![]() |
Modify record (reserved for operators) |
