Elective course planning

Simon Kristiansen, Matias Sørensen, Thomas Riis Stidsen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    Efficient planning increasingly becomes an indispensable tool for management of both companies and public organizations. This is also the case for high school management in Denmark, because the growing individual freedom of the students to choose courses makes planning much more complex. Due to reforms, elective courses are today an important part of the curriculum, and elective courses are a good way to make high school education more attractive for the students. In this article, the problem of planning the elective courses is modeled using integer programming and three different solution approaches are suggested, including a Branch-and-Price framework using partial Dantzig–Wolfe decomposition. Explicit Constraint Branching is used to enhance the solution process, both on the original IP model and in the Branch-and-Price algorithm. To the best of our knowledge, no exact algorithm for the Elective Course Planning Problem has been described in the literature before. The proposed algorithms are tested on data sets from 98 of the 150 high schools in Denmark. The tests show that for the majority of the problems, the optimal solution can be obtained within the one hour time bound. Furthermore the suggested algorithms achieve better results than the currently applied meta-heuristic.
    Original languageEnglish
    JournalEuropean Journal of Operational Research
    Volume215
    Issue number3
    Pages (from-to)713-720
    ISSN0377-2217
    DOIs
    Publication statusPublished - 2011

    Keywords

    • Elective course planning
    • Explicit Constraint Branching
    • Dantzig–Wolfe decomposition
    • Branch and Price
    • High school planning
    • Integer programming

    Fingerprint Dive into the research topics of 'Elective course planning'. Together they form a unique fingerprint.

    Cite this