Learning Heuristics for Combinatorial Optimization Problems on K-Partite Hypergraphs

Recently, deep neural networks have demonstrated remarkable performance in addressing combinatorial optimization challenges. The expressive power of graph neural networks combined with Reinforcement Learning (RL) enabled learning heuristics that rival or even surpass conventional methods. Such advancements have paved the way for Neural Combinatorial Optimization (NCO), an emerging paradigm that enables end-to-end heuristic learning without the reliance on expert knowledge. In this paper, we propose an NCO approach to learn heuristics for the vast family of Combinatorial Optimization Problems (COPs) defined on K-partite hypergraphs, including multi-dimensional assignment or scheduling problems. Central to our approach is the ability to represent sophisticated functions on K-partite hypergraphs, using a novel family of neural networks. We show that our heuristic competes with other ones in comparable settings and that our method can also be applied to more complex real-life assignment and scheduling problems.