Hybrid Loss Function for Graph Neural Networks: A Case Study on a Real-World Timetabling Problem
摘要
Graph Neural Networks have been successfully used to solve combinatorial optimization problems due to their ability to capture the underlying connections in data, exploit structural patterns, and handle instances with varying sizes. Nevertheless, the performance and generalization ability of these models can be further improved for complex optimization tasks, such as timetabling. To address this objective, this paper proposes a hybrid cost function combining an unsupervised differentiable loss component with a supervised one, for tackling a well-known rostering problem using Graph Neural Networks. The supervised loss component was selected as the standard cross-entropy, while the unsupervised one was designed to penalize possible infringements of the problem constraints based on their occurrence probability. An in-depth review of the literature indicated that this is the first paper using Graph Neural Networks for solving a timetabling task by optimizing a supervised-unsupervised cost function. Extensive experiments performed across three different Graph Neural Network architectures revealed that the proposed hybrid loss generated a significantly higher percentage of optimal solutions compared to the unsupervised and supervised versions, while obtaining a low number of unfeasible ones.