View article

In this paper we applied Benders’ decomposition to the Curriculum-Based Course Timetabling (CBCT) problem. The objective of the CBCT problem is to assign a set of lectures to time slots and rooms. Our approach was based on segmenting the problem into time scheduling and room allocation problems. The Benders’ algorithm was then employed to generate cuts that connected the time schedule and room allocation. We generated only feasibility cuts, meaning that most of the solutions we obtained from a mixed integer programming solver were infeasible, therefore, we also provided a heuristic in order to regain feasibility.

We compared our algorithm with other approaches from the literature for a total of 32 data instances. We obtained a lower bound on 23 of the instances, which were at least as good as the lower bounds obtained by the state-of-the-art, and on eight of these, our lower bounds were higher. On …