A New Adjustment of the Branch and Price Algorithm for University Course Timetabling

Abstract. In 2005 Avella and Vasil’Ev [2] 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 spe-cially 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. The nu-merical results show that the computing time of the presented branch and price algorithm is always less than that of branch and cut algo-rithm. Moreover, the number of subproblems and master problems of the presented branch and price algorithm depends on the structure of the problem. Finally, for all test instances the number of variables is very large that justifies the use of the branch and price algorithm for solving the problem.