Novas estratégias para obtenção de limitantes inferiores para o problema de tabela-horário de universidades

Abstract

The University Timetabling Problem (UTP) is one of the most researched topics in the field of combinatorial optimization. This problem consists of allocating a set of lectures to available rooms and periods (timetable) considering students and teachers requests and constraints. Several mathematical formulations for the UTP can be found in the literature once specificities of this problem can vary for each institution. The formulation considered in this work is based on courses curricula of an university, proposed in the second International Timetabling Competition (ITC-2007). So far, several methods based on integer linear programming have been proposed in the literature to obtain lower bounds for this minimization problem. Here, new strategies based on the divide and conquer principle are presented in order to obtain lower bounds for the problem. In this way, the original problem is partitioned with METIS library into sub-problems, each one solved by CPLEX solver. Computational experiments were performed on the ITC-2007 benchmark instances and the results were compared to the best lower bounds found in the literature. These results show the strategies proposed are able to improve the best known lower bounds for two of 21 instances tested and prove the optimality for another 15 instances.