{'fraction_non_alphanumeric': 0.02503755633450175, 'fraction_numerical': 0.005007511266900351, 'mean_word_length': 5.0, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Experimental Evaluation of Course Timetabling Algorithms

The goal of this report is to give an analysis of the run time distributions for the algorithms considered in the experimental evaluation of the Course Timetabling problem [8]. Furthermore we investigate the hardness of the instances produced by the random instance generator proposed by Rossi-Doria and Ben Paechter [8]. This analysis confirms the impression, gained during the configuration of the metaheuristics Simulated Annealing and Iterated Local Search at the Intellectics Group and suggested by the results on the SAT problem [11, 3, 10], that some instances can be substantially harder than others. By further studying the correlation of the hardness of the instances for several algorithms, we can deduce that the hardness seems to be an intrinsic aspect of an instance and does not only depend on the specific algorithm used to solve it. In addition to this, we study how the hardness of instances is influenced by some of the parameters of the instance generator. All analyses are done on a simplification of the problem in which only hard constraints are considered and the time computed is the time needed for finding a first feasible solution. The algorithms analyzed are Iterated Local Search (ILS), Ant Colony Optimization (ACO), Random Restart Local Search (RR.LS) and Simulated Annealing. For the latter we considered two alternatives: the winner of the automated tuning [1] (SA) and a variant which uses the Simulated Annealing criterion embedded in the local search described in [9] (SA.LS). More in detail, the first approach uses a completely random move selection strategy in which at each step the proposed move is randomly selected from the union of all the possible moves. The second approach, instead, searches, in the same order as in the local search, only a promising restricted part of the neighborhood. We refer to [9] for the description of the common neighborhood structure used by all these algorithms.