# Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks

arXiv: https://arxiv.org/abs/2603.19318 · HTML: https://mlsanity.com/paper/2603.19318/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 49 references that are in the map.
- First posted on arXiv 16 Mar 2026.

## Builds on (most cited first, 29 of 29)

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks](https://mlsanity.com/paper/2105.00956/) (2021)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Learning to Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [A Survey for Solving Mixed Integer Programming via Machine Learning](https://mlsanity.com/paper/2203.02878/) (2022)
- [A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2302.05636/) (2023)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [Learning to Compare Nodes in Branch and Bound with Graph Neural Networks](https://mlsanity.com/paper/2210.16934/) (2022)
- [Towards Foundation Models for Mixed Integer Linear Programming](https://mlsanity.com/paper/2410.08288/) (2024)
- [A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide](https://mlsanity.com/paper/2404.01039/) (2024)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Machine Learning for Cutting Planes in Integer Programming: A Survey](https://mlsanity.com/paper/2302.09166/) (2023)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (2024)
- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Graph Neural Networks for Job Shop Scheduling Problems: A Survey](https://mlsanity.com/paper/2406.14096/) (2024)
- [Distributed Constrained Combinatorial Optimization leveraging Hypergraph Neural Networks](https://mlsanity.com/paper/2311.09375/) (2023)
- [Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2404.12638/) (2024)
- [Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making](https://mlsanity.com/paper/1504.06002/) (2015)
- [SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch](https://mlsanity.com/paper/2412.15534/) (2024)
- [Learning to Optimize for Mixed-Integer Non-linear Programming with Feasibility Guarantees](https://mlsanity.com/paper/2410.11061/) (2024)
- [Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning](https://mlsanity.com/paper/2310.11845/) (2023)
- [Learning for Spatial Branching: An Algorithm Selection Approach](https://mlsanity.com/paper/2204.10834/) (2022)
- [On Representing Convex Quadratically Constrained Quadratic Programs via Graph Neural Networks](https://mlsanity.com/paper/2411.13805/) (2024)
- [NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs](https://mlsanity.com/paper/2410.03720/) (2024)
- [Search Strategy Generation for Branch and Bound Using Genetic Programming](https://mlsanity.com/paper/2412.09444/) (2024)

## Abstract (arXiv)

Complex real-world optimization problems often involve both discrete decisions and nonlinear relationships between variables. Many such problems can be modeled as polynomial-objective integer programs, encompassing cases with quadratic and higher-degree variable interactions. Nonlinearity makes them more challenging than their linear counterparts. In this paper, we propose a hypergraph neural network (HNN) based method to solve polynomial-objective integer programming (POIP). Besides presenting a high-degree-term-aware hypergraph representation to capture both high-degree information and variable-constraint interdependencies, we also propose a hypergraph neural network, which integrates convolution between variables and high-degree terms alongside convolution between variables and constraints, to predict solution values. Finally, a search process initialized from the predicted solutions is performed to further refine the results. Comprehensive experiments across a range of benchmarks demonstrate that our method consistently outperforms both existing learning-based approaches and state-of-the-art solvers, delivering superior solution quality with favorable efficiency. Note that our experiments involve both polynomial objectives and constraints, demonstrating our HNN's versatility for general POIP problems and highlighting its advancement over the existing literature.