High School Planning The Class Packing Problem Exact Solution Methods for Real-Life Instances

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 Branch-ing. 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 MI