Dantzig-Wolfe Decomposition of the Daily Course Pattern Formulation for Curriculum-Based Course Timetabling

Niels-Christian Fink Bagger*, Matias Sørensen, Thomas Jacob Riis Stidsen

*Corresponding author for this work

    Research output: Contribution to journalJournal articleResearchpeer-review

    25 Downloads (Pure)

    Abstract

    In this paper, we considered the problem of Curriculum-Based Course Timetabling, i.e., assigning weekly lectures to a time schedule and rooms. We developed a Column Generation algorithm based on a pattern formulation of the time scheduling part of the problem by Bagger et al. (2016). The pattern formulation is an enumeration of all schedules by which each course can be assigned on each day; it is a lower bounding model. Pattern enumeration has also been considered in Burke et al. (2008), where the authors enumerated all schedules to which each curriculum can be assigned on each day. We applied the Dantzig-Wolfe reformulation, so each column corresponded to a schedule for an entire day.
    We solved the reformulation with the Column Generation algorithm, where each pricing problem generated a full schedule for a single day. We provided a pre-processing technique that, on average, removed approximately 45% of the pattern variables in the pricing problems. We then extended the pre-processing technique into inequalities that we added to the model. Lastly, we describe how we applied Local Branching to the pricing problem by using the columns generated
    in previous iterations. We compare the lower bounds we obtained, with other methods from literature, on 20 data instances of real-world applications. For 16 instances the optimal solutions are known, but the remaining four are still open. Our approach improved the best-known lower bound for all four open instances, and decreased the average gap from 24% to 11%.
    Original languageEnglish
    JournalEuropean Journal of Operational Research
    Volume272
    Issue number2
    Pages (from-to)430-446
    Number of pages17
    ISSN0377-2217
    DOIs
    Publication statusPublished - 2018

    Keywords

    • Timetabling
    • Integer programming
    • Education
    • Column generation
    • Local branching

    Fingerprint Dive into the research topics of 'Dantzig-Wolfe Decomposition of the Daily Course Pattern Formulation for Curriculum-Based Course Timetabling'. Together they form a unique fingerprint.

    Cite this