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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Hybrid Loss Function for Graph Neural Networks: A Case Study on a Real-World Timetabling Problem

  • Laura-Maria Cornei

摘要

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.