abstract

• University timetabling is a real-world problem frequently encountered in higher education institutions. It has been studied by many researchers who have proposed a wide variety of solutions. Measuring the variation of the performance of solution approaches across instance spaces is a critical factor for algorithm selection and algorithm configuration, but because of the diverse conditions that define the problem within different educational contexts, measurement has not been formally addressed within the university timetabling context. In this paper, we propose a set of metrics to predict the performance of combinatorial optimization algorithms that generate initial solutions for university timetabling instances. These metrics, derived from the fields of enumerative combinatorics and graph coloring, include size-related instance properties, counting functions, feature ratios and constraint indexes evaluated through a feature selection methodology that, based on regression algorithms, characterizes the empirical hardness of a subspace of synthetically generated instances. The results obtained with this methodology show the current need not only to develop solution strategies for particular cases of the problem, but also to produce a formal description of the conditions that make instance spaces hard to solve, in order to improve and integrate the available solution approaches. © 2020, Springer Science Business Media, LLC, part of Springer Nature.
• University timetabling is a real-world problem frequently encountered in higher education institutions. It has been studied by many researchers who have proposed a wide variety of solutions. Measuring the variation of the performance of solution approaches across instance spaces is a critical factor for algorithm selection and algorithm configuration, but because of the diverse conditions that define the problem within different educational contexts, measurement has not been formally addressed within the university timetabling context. In this paper, we propose a set of metrics to predict the performance of combinatorial optimization algorithms that generate initial solutions for university timetabling instances. These metrics, derived from the fields of enumerative combinatorics and graph coloring, include size-related instance properties, counting functions, feature ratios and constraint indexes evaluated through a feature selection methodology that, based on regression algorithms, characterizes the empirical hardness of a subspace of synthetically generated instances. The results obtained with this methodology show the current need not only to develop solution strategies for particular cases of the problem, but also to produce a formal description of the conditions that make instance spaces hard to solve, in order to improve and integrate the available solution approaches. © 2020, Springer Science%2bBusiness Media, LLC, part of Springer Nature.

authors

• de la Rosa-Rivera F.
• Nava Muñoz Sandra Edith
• Núñez Varela José Ignacio
• Puente Montejano César Augusto

publication date

• 2020-01-01

published in

• Journal of Scheduling  Journal

keywords

• Empirical hardness; Feature selection; Instance generator; University timetabling Combinatorial mathematics; Combinatorial optimization; Feature extraction; Graph algorithms; Hardness; Scheduling; Algorithm configurations; Combinatorial optimization algorithm; Educational context; Enumerative combinatorics; Higher education institutions; Instance generator; Regression algorithms; University timetabling; Solution mining

Digital Object Identifier (DOI)

• 10.1007/s10951-020-00641-y

start page

end page