A quantum heuristic for the school timetabling problem

Abstract

School timetabling é uma variação do Problema de Alocação de Horários que busca uma alocação periódica de aulas para alunos e professores de uma escola, que deve seguir um conjunto de restrições fortes e fracas. Timetabling é um problema NP-Hard e, por causa de sua dificuldade, o uso de heurísticas para solucionar o problema é uma prática comum. Quando apenas as restrições fortes são consideradas, o problema timetabling pode ser reduzido para a coloração de grafos e a similaridade entre esses problemas tem motivado o uso de heurísticas para coloração de grafos como um meio de solucionar o problema de timetabling. Esse trabalho propõe uma otimização em dois passos para solucionar o problema de school timetabling, onde no primeiro passo o problema é reduzido para coloração de grafos e o circuito quântico do Quantum Approximate Optimization Algorithm (QAOA) para a solução do problema do número cromático é usado para resolver as restrições fortes e no segundo passo o processo de otimização clássico do QAOA é usado para solucionar as restrições fracas. A heurística foi testada em instâncias de benchmark do banco de dados do XHSTT. Os circuitos quânticos do trabalho possuíam até 189 qubits e foram simulados em um ambiente sem ruído. Essa pesquisa e seus resultados são um trabalho seminal no uso do QAOA como heurística para o problema de timetabling.

Abstract: School timetabling is a variation of the Timetabling problem that searches for a periodic scheduling of lessons for classes and teachers of a school, that must meet a set of hard and soft constraints. Timetabling is an NP-Hard problem and because of its difficulty, the use of heuristics to address it is a common practice. When only the hard constraints are considered, the timetabling problem can be reduced to graph vertex coloring and the similarity between both problems has motivated the use of graph coloring heuristics as a means to tackle the timetabling problem. We propose to tackle the school timetabling problem by applying a Two-stage optimization, where in the first stage we reduce it to a graph coloring problem and use the Quantum Approximate Optimization Algorithm (QAOA) quantum circuit for solving the chromatic number problem to address the hard constraints and on the second stage we address the soft constraints of the timetabling problem by using the classical optimization process of QAOA. We tested our heuristic using benchmark instances from the XHSTT dataset and we simulated quantum circuits up to 189 qubits in a noiseless environment. We consider this research and its findings a seminal work in using QAOA as a heuristic for the timetabling problem.