Benders’ Decomposition for Curriculum-Based Course Timetabling

Niels-Christian F. Bagger*, Matias Sørensen, Thomas R. Stidsen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

401 Downloads (Pure)

Abstract

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.
Original languageEnglish
JournalComputers and Operations Research
Volume91
Pages (from-to)178-189
ISSN0305-0548
DOIs
Publication statusPublished - 2018

Fingerprint

Dive into the research topics of 'Benders’ Decomposition for Curriculum-Based Course Timetabling'. Together they form a unique fingerprint.

Cite this