A new lower bound for curriculum-based course timetabling

In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (CTT), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing up the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones).