Publication details
Penalising Patterns in Timetables: Novel Integer Programming Formulations
| Basic information | |
|---|---|
| Original title: | Penalising Patterns in Timetables: Novel Integer Programming Formulations |
| Authors: | Edmund K. Burke, Jakub Mareček, Andrew J. Parkes, Hana Rudová |
| Further information | |
|---|---|
| Citation: | BURKE, Edmund K.  - MAREČEK, Jakub - PARKES, Andrew J. - RUDOVÁ, Hana. Penalising Patterns in Timetables: Novel Integer Programming Formulations. In Operations Research Proceedings 2007. Berlin : Springer, 2008. ISBN 978-3-540-77902-5, pp. 409-414. |
| Original language: | English |
| Field: | Informatika |
| WWW: |  URL, DOI |
| Type: | Article in Proceedings |
| Keywords: | integer programming; course timetabling; patterns |
Many complex timetabling problems, such as university course timetabling and employee rostering, have an underpinning graph colouring component, a pattern penalisation component and a number of side constraints. In real-life settings, it might be relatively easy to come up with feasible solutions to instances of graph colouring, which correspond to hard constraints such as ``each student attends all events of courses of his choice and no student can be in two rooms at the same time'' even for hundreds of events and hundreds of distinct enrollments. Much more challenging are requirements such as ``students should not have gaps in their individual daily timetables'', which often make the problem over-constrained. On the example of the Udine Course Timetabling Problem, this paper studies several integer programming formulations of such pattern penalising constraints.
Related projects:
