arXiv:2603.19318cs.NEcs.LG2026-03中稿 · publication in CPA…

用超图神经网络求解非线性整数规划问题,效果优于传统方法。

Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks

  • 构建高阶项感知的超图表示,捕捉变量与约束的复杂关系。
  • 模型在多个基准上超越现有学习方法和顶尖求解器,解的质量更优。
  • 适合处理带多项式目标和约束的复杂优化问题,尤其适合工程建模场景。

现实世界中的复杂优化问题常涉及离散决策与变量间的非线性关系。许多此类问题可建模为多项式目标整数规划(POIP),包含二次及更高次变量交互。非线性使这类问题比线性情形更难求解。本文提出一种基于超图神经网络(HNN)的求解方法。首先设计高阶项感知的超图表示,以捕获高阶信息及变量-约束间的依赖关系;其次构建融合变量-高阶项卷积、变量-约束卷积的HNN,用于预测解值;最后基于预测解启动搜索过程进行进一步优化。在多个基准上的实验表明,该方法在解质量与效率方面均显著优于现有学习方法与先进求解器,且适用于含多项式目标与约束的通用POIP问题,体现了对现有文献的实质性推进。

原文摘要 · Abstract (English)

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.

整数规划超图网络非线性优化机器学习求解

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。