Journal article
Benders’ Decomposition for Curriculum-Based Course Timetabling
Department of Management Engineering, Technical University of Denmark1
Management Science, Department of Management Engineering, Technical University of Denmark2
Operations Research, Management Science, Department of Management Engineering, Technical University of Denmark3
MaCom A/S4
Department of Applied Mathematics and Computer Science, Technical University of Denmark5
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 two of the instances, our lower bound was an improvement of the currently best-known. Lastly, we compared our decomposition to the model without the decomposition on an additional six instances, which are much larger than the other 32.
To our knowledge, this was the first time that lower bounds were calculated for these six instances.
Language: | English |
---|---|
Year: | 2018 |
Pages: | 178-189 |
ISSN: | 1873765x and 03050548 |
Types: | Journal article |
DOI: | 10.1016/j.cor.2017.10.009 |
ORCIDs: | Bagger, Niels-Christian F. and Stidsen, Thomas R. |