Bibliographic Metadata

Algorithm selection and performance prediction for the examination timetabling problem / von Olga Zhukova
AuthorZhukova, Olga
CensorMusliu, Nysret
PublishedWien, 2018
Descriptionxiii, 158 Seiten : Diagramme
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2018
Document typeThesis (Diplom)
Keywords (EN)Machine Learning / Examination Timetabling / Algorithm Selection / Performance Prediction
URNurn:nbn:at:at-ubtuw:1-114245 Persistent Identifier (URN)
 The work is publicly available
Algorithm selection and performance prediction for the examination timetabling problem [6.31 mb]
Abstract (English)

The Examination Timetabling Problem (ETP)is an important task that appears periodically at universities, colleges and schools. A general definition of the timetabling problem which covers most cases is as follows: a timetabling problem is a problem with four parameters: T, a finite set of times; R, a finite set of resources; M, a finite set of exams; and C, a finite set of constraints. The problem is to assign times and resources to the exams so as to satisfy the constraints as much as possible. However, due to its practical focus, a particular point of interest is the formulation presented on the ITC 2007. Examination timetabling has been studied for years, and NP-completeness of some formulations was proven. Therefore exact methods can not always solve large instances in a reasonable time. Although a lot of different heuristics have been developed, there is no known algorithm that dominates on all problem instances. Moreover, according to the No Free Lunch Theorem, this situation is in fact impossible. Therefore, in order to achieve better performance, we can choose the best performing heuristic for a particular instance using a set of predefined instance characteristics. This task is commonly known as the Algorithm Selection Problem (AS). Additionally, it might be practically useful to be able to predict the quality of the solution obtained by a certain solver on a given instance. This problem has been named the Algorithm Performance Prediction Problem (APP). In this thesis, we present the solution for the Algorithm Selection and the Algorithm Performance Prediction Problems for the ITC2007 formulation of the ETP using Machine Learning techniques. For that, we introduce a set of characteristics which consists of 196 features. Also, we collect 3 State-Of-The-Art heuristics for the ETP and run them on the dataset of 2243 real-world and artificially generated instances. We find none of the algorithms outperforms the others for all instances. Subsequently, we use 6 classification algorithms and 9 regression techniques for solving the AS and the APP problems respectively. Additionally, we investigate the influence of the parameter settings and preprocessing techniques on estimator performance. Moreover, we inspect the importance of particular feature groups for the AS and APP problems. As a result, we succeed in the building of rather accurate performance prediction models for the APP and construction of the AS solver that outperforms all of their underlying heuristics individually.

The PDF-Document has been downloaded 13 times.