Publication details
Strengthened Integer Programming Formulation of Constraints Counting Matches of Patterns in Timetables
| Basic information | |
|---|---|
| Original title: | Strengthened Integer Programming Formulation of Constraints Counting Matches of Patterns in Timetables |
| Authors: | Edmund K. Burke, Jakub Mareček, Hana Rudová |
| Further information | |
|---|---|
| Citation: | BURKE, Edmund K.  - MAREČEK, Jakub - RUDOVÁ, Hana. Strengthened Integer Programming Formulation of Constraints Counting Matches of Patterns in Timetables. 2007. |
| Original language: | English |
| Field: | Informatika |
| WWW: |  http://www.or2007.de |
| Type: | Conference abstract |
| Keywords: | integer programming; course timetabling; patterns |
Complex real-world problems in timetabling, especially university course timetabling and employee rostering, have an underpinning graph colouring component, a pattern matching component and a number of side constraints. Problems with pattern matching constraints such as ``students should not have more than three lectures in a row and five lectures in a day'' tend to be over-constrained, making it necessary for integer programming formulations to implement pattern matching using either goal programming or to implement soft constraints, which count the number of occurrences of undesirable patterns. This paper introduces an integer programming formulation, where the number of such occurrences is counted both locally and by enumeration of patterns over daily timetables. With a number of strong valid constraints taking advantage of the interplay of the two methods of counting, this formulation seems to outperform any of its constituent parts.
Related projects:
