Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks

• URL: http://arxiv.org/abs/2603.19318v1
• Date: Mon, 16 Mar 2026 10:59:03 GMT
• Title: Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks
• Abstract summary: Complex real-world optimization problems often involve both discrete decisions and nonlinear relationships between variables.<n>We propose a hypergraph-aware neural network (HNN) based method to solve-objective integer programming (POIP)
• Score: 15.25020090502185
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Systematic Analysis of Automatic Differentiation versus Discretization-based Constraints for Physics-Informed PDE Solvers [5.821193246951147]
  Physics-informed neural networks (PINNs) represent a growing frontier using artificial intelligence to solve partial differential equations (PDEs)<n>We conduct systematic experiments across a wide spectrum of problems, from simple linear Poisson to high-Mach hypersonic flows with strong discontinuities.<n>Our results reveal a consistent trend: as nonlinearity strengthens, the accuracy advantage of discretization-based constraints becomes increasingly pronounced.
  arXiv  Detail & Related papers  (2026-09-07T12:44:35Z)
• DeePoly: A High-Order Accuracy Scientific Machine Learning Framework for Function Approximation and Solving PDEs [5.483488375189695]
  This work introduces a novel framework that transforms the Dee solution to a two-stage approach.<n>The strategic combination leverages the strengths of both methods.<n>This approach also serves as the open-source project also serves as the paper.
  arXiv  Detail & Related papers  (2025-06-05T04:10:52Z)
• A Simultaneous Approach for Training Neural Differential-Algebraic Systems of Equations [0.4935512063616847]
  We study neural differential-algebraic systems of equations (DAEs), where some unknown relationships are learned from data.<n>We apply the simultaneous approach to neural DAE problems, resulting in a fully discretized nonlinear optimization problem.<n>We achieve promising results in terms of accuracy, model generalizability and computational cost, across different problem settings.
  arXiv  Detail & Related papers  (2025-04-07T01:26:55Z)
• Learning and discovering multiple solutions using physics-informed neural networks with random initialization and deep ensemble [10.047968926134363]
  We explore the capability of physics-informed neural networks (PINNs) to discover multiple solutions.<n> PINNs can effectively uncover multiple solutions to nonlinear ordinary and partial differential equations.<n>We propose utilizing PINN-generated solutions as initial conditions or initial guesses for conventional numerical solvers.
  arXiv  Detail & Related papers  (2025-03-08T19:32:22Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Tunable Complexity Benchmarks for Evaluating Physics-Informed Neural Networks on Coupled Ordinary Differential Equations [64.78260098263489]
  In this work, we assess the ability of physics-informed neural networks (PINNs) to solve increasingly-complex coupled ordinary differential equations (ODEs) We show that PINNs eventually fail to produce correct solutions to these benchmarks as their complexity increases. We identify several reasons why this may be the case, including insufficient network capacity, poor conditioning of the ODEs, and high local curvature, as measured by the Laplacian of the PINN loss.
  arXiv  Detail & Related papers  (2022-10-14T15:01:32Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• Message Passing Neural PDE Solvers [60.77761603258397]
  We build a neural message passing solver, replacing allally designed components in the graph with backprop-optimized neural function approximators. We show that neural message passing solvers representationally contain some classical methods, such as finite differences, finite volumes, and WENO schemes. We validate our method on various fluid-like flow problems, demonstrating fast, stable, and accurate performance across different domain topologies, equation parameters, discretizations, etc., in 1D and 2D.
  arXiv  Detail & Related papers  (2022-02-07T17:47:46Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)
• High Dimensional Level Set Estimation with Bayesian Neural Network [58.684954492439424]
  This paper proposes novel methods to solve the high dimensional Level Set Estimation problems using Bayesian Neural Networks. For each problem, we derive the corresponding theoretic information based acquisition function to sample the data points. Numerical experiments on both synthetic and real-world datasets show that our proposed method can achieve better results compared to existing state-of-the-art approaches.
  arXiv  Detail & Related papers  (2020-12-17T23:21:53Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.