A column generation approach to high school timetabling modeled as a multicommodity flow problem

School timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a predetermined period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, often it is difficult to find even a feasible solution. Several techniques have been developed in the literature to tackle the high school timetabling problem. Since the use of exact methods, as mathematical programming techniques, are considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this paper we propose a multicommodity flow model for the high school timetabling problem. In addition, we apply Dantzig-Wolfe decomposition to the proposed model, propose a column generation algorithm, and present experimental results on well known instances of the problem. The results show that the lower bounds obtained through our approach are tight and can be generated faster than previous approaches reported in the literature.