polito.it
Politecnico di Torino (logo)

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

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

[img]
Preview
PDF (Tesi_di_laurea) - Tesi
Document access: Anyone
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. 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.

Relators: Roberto Tadei
Academic year: 2017/18
Publication type: Electronic
Number of Pages: 51
Subjects:
Corso di laurea: Corso di laurea magistrale in Communications And Computer Networks Engineering (Ingegneria Telematica E Delle Comunicazioni)
Classe di laurea: New organization > Master science > LM-27 - TELECOMMUNICATIONS ENGINEERING
Ente in cotutela: TECHNISCHE UNIVERSITAT DARMSTADT, Faculty of Engineering (GERMANIA)
Aziende collaboratrici: UNSPECIFIED
URI: http://webthesis.biblio.polito.it/id/eprint/8205
Modify record (reserved for operators) Modify record (reserved for operators)