Tianyi Liu
A Scalable Graph-based Mixed-Integer Linear Programming Approach for the Examination Timetabling Problem.
Rel. Roberto Tadei. Politecnico di Torino, Corso di laurea magistrale in Communications And Computer Networks Engineering (Ingegneria Telematica E Delle Comunicazioni), 2018
|
Preview |
PDF (Tesi_di_laurea)
- Tesi
Licenza: 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
Relatori
Anno Accademico
Tipo di pubblicazione
Numero di pagine
Corso di laurea
Classe di laurea
Ente in cotutela
URI
![]() |
Modifica (riservato agli operatori) |
