Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks
This addresses complex optimization problems with discrete decisions and nonlinear relationships, offering a versatile solution for real-world applications, though it appears incremental as it builds on neural network methods for optimization.
The paper tackles polynomial-objective integer programming problems by proposing a hypergraph neural network method that captures high-degree interactions and variable-constraint dependencies, achieving superior solution quality and efficiency compared to existing learning-based approaches and state-of-the-art solvers.
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.