Elective course planning

Simon Kristiansen

doi:10.1016/j.ejor.2011.06.039

2011-12-01

PRE

Simon Kristiansen *

Matias Sørensen

Thomas Stidsen

DOI：10.1016/j.ejor.2011.06.039

原文链接

原文求助

摘要

En 中文

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. (C) 2011 Elsevier B.V. All rights reserved.

Keyword:

Elective course planning

High school planning

Integer programming

Dantzig-Wolfe decomposition

Branch and Price

Explicit Constraint Branching