Benders’ Decomposition for Curriculum-Based Course Timetabling

Research output: Contribution to journalJournal article – Annual report year: 2018Researchpeer-review

Standard

Benders’ Decomposition for Curriculum-Based Course Timetabling. / Bagger, Niels-Christian F.; Sørensen, Matias; Stidsen, Thomas R.

In: Computers & Operations Research, Vol. 91, 2018, p. 178-189.

Research output: Contribution to journalJournal article – Annual report year: 2018Researchpeer-review

Harvard

APA

CBE

MLA

Vancouver

Author

Bibtex

@article{12a2d9f72d9a4ec6a7c01618172d60db,
title = "Benders’ Decomposition for Curriculum-Based Course Timetabling",
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.",
author = "Bagger, {Niels-Christian F.} and Matias S{\o}rensen and Stidsen, {Thomas R.}",
year = "2018",
doi = "10.1016/j.cor.2017.10.009",
language = "English",
volume = "91",
pages = "178--189",
journal = "Computers & Operations Research",
issn = "0305-0548",
publisher = "Pergamon Press",

}

RIS

TY - JOUR

T1 - Benders’ Decomposition for Curriculum-Based Course Timetabling

AU - Bagger, Niels-Christian F.

AU - Sørensen, Matias

AU - Stidsen, Thomas R.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

U2 - 10.1016/j.cor.2017.10.009

DO - 10.1016/j.cor.2017.10.009

M3 - Journal article

VL - 91

SP - 178

EP - 189

JO - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

ER -