Neural Combinatorial Optimization on Hypergraphs

Along with AI computing shining in scientific discovery, neural combinatorial optimization (NCO) has shown promise across diverse problems. Yet, existing neural solvers struggle to solve combinatorial optimization problems (COPs) on large-scale hypergraphs (e.g., hypergraph max-cut, hypergraph partitioning), due to limited computational frameworks. In this work, we propose HyperNCO, an NCO framework for hypergraph COPs. We contribute: (I) A unified one-hot encoded polynomial unconstrained binary optimization (PUBO) formulation for modeling hypergraph COPs; (II) GPU-accelerated algorithms for one-hot encoded PUBO problems; (III) A Gini coefficient-based continuous relaxation annealing strategy to ensure high-quality solutions while preventing convergence to local optima. Experimental results demonstrate that HyperNCO achieves competitive solution quality compared to existing heuristics and state-of-the-art neural solvers, while offering significant advantages in computational efficiency and framework generality.