Generalizing the Structure of a University Timetabling Solver for Flexible Automatic Algorithm Configuration

This paper explores how a state-of-the-art hybrid metaheuristic for Curriculum-based Course Timetabling, composed of several algorithmic building blocks, can be deconstructed and reconfigured to produce a better algorithm. In particular, an Iterated Local Search strategy is proposed that allows reordering, chaining and looping together the building blocks, and to configure both the global and local search components. This then gives irace, an automatic configurator, the flexibility to explore configurations instantiating different hybrid metaheuristic configurations that outperform the original method. Since using such a configurator can be seen as a black-box process, we provide a comprehensive analysis that determines which parameters are decisive in obtaining the best configurations, finds relevant associations, and analyses the distribution of crucial parameters. In particular, we find that the best configurations discard the simulated annealing component of the original algorithm, as well as some neighborhood operators. The range of necessary algorithmic mechanisms to achieve the new state-of-the-art performance can therefore be reduced.