Journal article
Integer programming for the generalized high school timetabling problem
Recently, the XHSTT format for high school timetabling was introduced. It provides a uniform way of modeling problem instances and corresponding solutions. The format supports a wide variety of constraints, and currently 38 real-life instances from 11 different countries are available. Thereby, the XHSTT format serves as a common ground for researchers within this area.
This paper describes the first exact method capable of handling an arbitrary instance of the XHSTT format. The method is based on a mixed-integer linear programming (MIP) model, which is solved in two steps with a commercial general-purpose MIP solver. Computational results show that our approach is able to find previously unknown optimal solutions for 2 instances of XHSTT and proves optimality of 4 known solutions.
For the instances not solved to optimality, new non-trivial lower bounds were found in 11 cases, and new best known solutions were found in 9 cases. Furthermore, the approach is compared with the finalists of Round 2 of the International Timetabling Competition 2011 and is shown to be competitive with one of the finalists.
Language: | English |
---|---|
Publisher: | Springer US |
Year: | 2015 |
Pages: | 377-392 |
ISSN: | 10991425 and 10946136 |
Types: | Journal article |
DOI: | 10.1007/s10951-014-0405-x |
ORCIDs: | Stidsen, Thomas Riis |