Beta 1

Title The Class Packing Problem : Exact Solution Methods for Real-Life Instances
Author Kristiansen, Simon
Sørensen, Matias
Supervisor Stidsen, Thomas K. (Operations Research, Department of Management Engineering, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2010
Abstract 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.
Imprint Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Pages 162
Original PDF master.pdf (2.01 MB)
Admin Creation date: 2010-02-01    Update date: 2010-02-01    Source: dtu    ID: 257515    Original MXD