EURO 2025 Leeds
Abstract Submission

2391. Solving Polynomial Integer Programming with Hypergraph Neural Network

Invited abstract in session WB-38: Optimization and Machine Learning: Methodological Advances, stream Data Science meets Optimization.

Wednesday, 10:30-12:00
Room: Michael Sadler LG19

Authors (first author is the speaker)

1. Minshuo Li
Mathematics & Computer Science, Eindhoven University of Technology
2. Yaoxin Wu
Eindhoven University of Technology
3. Pavel Troubil
Dassault Systèmes
4. Yingqian Zhang
Industrial Engineering, TU Eindhoven
5. Wim Nuijten
IE&IS, Technical University of Eindhoven

Abstract

Complex real-world optimization problems often involve nonlinear relationships (either as constraints or objectives) resulting from physical laws, statistical measures, nonlinear regression, and other factors. While nonlinear programming can model such nonlinear relationships, existing solvers become computationally prohibitive for large-scale problems with numerous variables and constraints. This paper aims to design a hypergraph neural network (HNN)-based framework to accelerate the solvers for general polynomial integer programming (PIP) problems, a critical subclass of nonlinear mathematical problems. Specifically, an HNN is proposed to learn representations of general PIP problems, capturing deep information from polynomial terms. Then the HNN is trained to predict initial solutions that, after feasibility repair, become high-quality solutions for PIP problems. Experimental results on quadratic instances show that the HNN-based framework significantly enhances the solution quality of exact solvers and outperforms another learning-based method. Tests on higher-order polynomial instances are considered for further validation. Moreover, the proposed HNN can be applied to other learning targets with minor adjustments, providing a promising general pathway for addressing a broad spectrum of nonlinear combinatorial optimization problems.

Keywords

Status: accepted

Back to the list of papers