Integer programming for the generalized high school timetabling problem

Simon Kristiansen, Matias Sørensen, Thomas Riis Stidsen

    Research output: Contribution to journalJournal articlepeer-review

    852 Downloads (Pure)

    Abstract

    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.
    Original languageEnglish
    JournalJournal of Scheduling
    Volume18
    Issue number4
    Pages (from-to)377-392
    Number of pages16
    ISSN1094-6136
    DOIs
    Publication statusPublished - 2015

    Keywords

    • High school timetabling
    • Integer programming
    • International Timetabling Competition 2011
    • XHSTT
    • Scheduling
    • Computational results
    • Corresponding solutions
    • High school
    • High school timetabling problems
    • Mixed integer linear programming
    • Optimal solutions
    • Timetabling

    Fingerprint

    Dive into the research topics of 'Integer programming for the generalized high school timetabling problem'. Together they form a unique fingerprint.

    Cite this