||The Class Packing Problem : Exact Solution Methods for Real-Life Instances
||Stidsen, Thomas K. (Operations Research, Department of Management Engineering, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||Many timetabling and assignment problems at the Danish High Schools are evident candidates for
applying Operational Research. Among these is the Class Packing Problem. This problem is concerned
with the issue of assigning students to elective course classes given their requests, subject to various
resource constraints. The small Danish company MaCom A/S has developed a metaheuristic based
solver for this problem, which is part of their software product Lectio. It is the goal of this thesis to
evaluate the performance of the algorithm in Lectio and to find the best choice of an exact algorithm
for the CPP.
The CPP is modeled as a NP-hard Integer Programming model, and Dantzig-Wolfe decomposition
and Column Generation are applied to attempt to speed up the solution process. To establish integer
solutions, the Column Generation algorithm is encapsulated in a Branch-and-Price framework. Two
different branching schemes are tested, Standard Variable Branching and Explicit Constraint Branching.
98 real-life instances are attempted solved to optimality using both BnP and solving the NP-hard
model using the CPLEX MIP solver.
The performance of the BnP algorithms is compared to the basic model solved directly in a MIP
solver. Furthermore some ECB constraints are added to the basic model to enhance the solution
process. This shows that the direct model with ECB constraints outperforms not only the pure direct
model, but also the BnP algorithm. This is a surprising result and suggests further research on ECB.
The BnP algorithm with SVB has proven itself to be useless for this problem.
Two aspects of the CPP, which are highly requested by the high schools, have been incorporated in
the solvers of this thesis. These are the use of weights on course requests and the minimization of represented
common classes in each elective course class. These extensions are not currently implemented
in Lectio, but has shown to provide significant improvement of solution quality.
It is concluded that in average an exact method does not provide significant better results than
MaComs current algorithm. However for some high schools the improvement is big. For these schools
it is shown that even with a timelimit of two minutes, an exact algorithm provides superior results to
those of Lectio.
||Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Creation date: 2010-02-01
Update date: 2010-02-01