A new adjustment of the branch and price algorithm for university course timetabling

Abstract

In 2005 Avella and Vasil'Ev \cite{vas} presented an efficient cutting plane algorithm for solving an integer binary programming formulation of the university course timetabling problem (UCTP). Here, we present a new and efficient adjustment of the branch and price algorithm for solving the same formulation of UCTP. In every iteration of the branch and price algorithm, the column generation algorithm is used for solving the linear programming relaxation. For the first time, in this paper the set packing constraints of the UCTP formulation are chosen as the specially structured constraints of the column generation algorithm. Then, a new efficient two phase heuristic method is presented for solving the set packing problem. The resulting adjusted column generation is used within a branch and price algorithm and a comparison is performed with the cutting plane algorithm presented by Avella and Vasil'Ev.