Performance de dois solvers na Resolução da Metaheurística Fix and Optimize Aplicado ao Problema de High School Timetabling
Resumo
O problema da Grade Horária Escolar do Ensino Médio (High Scholl Timetabling – HSTT) consiste em construir a escala semanal de uma instituição de ensino. O problema é caracterizado por um grande número de variáveis e restrições, fazendo que para instancias de médio e grande porte torna-se impossível resolve-lo manualmente, ou em alguns casos até métodos exatos são incapazes de encontrar boas soluções em um tempo computacional viável, obrigando os pesquisadores adotarem o uso de heurísticas. Neste trabalho testaremos dois solvers de programação inteira mista para a solução da heurística de fix-and-optimize. Esta heurística é um método que consiste em fixar uma parte das variáveis, criando subproblemas muito menores, possibilitando sua solução através de métodos exatos e então repetindo o processo de fixação até todas as variáveis serem deixadas livres para a otimização. Para solucionar a parte exata da heurística usaremos os solvers GUROBI 7.0.2 e CPLEX 12.6.2 e então comparar os resultados para avaliar qual seria a melhor opção a ser usada neste tipo de problema. Como resultado o solver GUROBI teve um melhor desempenho em quatro das cinco instancias estudadas.