用超图神经网络解决非线性整数规划问题,无需标注数据即可端到端优化。
BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks
- 将非线性整数规划转化为可微多项式损失函数,通过超图结构建模
- 在合成与真实数据集上优于传统方法,支持大规模并行训练
- 适合需要快速求解复杂离散优化问题的研究者和工程师
二值(0-1)整数规划(BIP)在需要离散决策的科学领域至关重要。随着人工智能计算的发展,近年研究尝试用神经网络求解整数线性规划(ILP)问题,但难以应对非线性挑战。现有先进分支定界切割求解器采用线性松弛处理非线性,导致辅助变量指数增长,计算成本剧增。为此,我们提出BIPNN(Binary Integer Programming Neural Network),一种基于超图神经网络(HyperGNN)的无监督学习框架,用于求解非线性BIP问题。具体而言,BIPNN将受约束、离散且非线性的(sin、log、exp)优化问题重构成无约束、可微且多项式的损失函数。该重构基于多项式形式的BIP目标与超图结构之间的精确一一映射关系,使得HyperGNN可在无监督条件下端到端优化BIP问题。在此基础上,我们设计了基于GPU加速与连续退火增强的训练流程,使BIPNN能通过简单的梯度下降并行优化大规模非线性项,显著降低训练成本,同时保证生成离散且高质量的解。在合成及真实世界数据集上的大量实验表明,本方法具有明显优势。
原文摘要 · Abstract (English)
Binary (0-1) integer programming (BIP) is pivotal in scientific domains requiring discrete decision-making. As the advance of AI computing, recent works explore neural network-based solvers for integer linear programming (ILP) problems. Yet, they lack scalability for tackling nonlinear challenges. To handle nonlinearities, state-of-the-art Branch-and-Cut solvers employ linear relaxations, leading to exponential growth in auxiliary variables and severe computation limitations. To overcome these limitations, we propose BIPNN (Binary Integer Programming Neural Network), an unsupervised learning framework to solve nonlinear BIP problems via hypergraph neural networks (HyperGNN). Specifically, BIPNN reformulates BIPs-constrained, discrete, and nonlinear (sin, log, exp) optimization problems-into unconstrained, differentiable, and polynomial loss functions. The reformulation stems from the observation of a precise one-to-one mapping between polynomial BIP objectives and hypergraph structures, enabling the unsupervised training of HyperGNN to optimize BIP problems in an end-to-end manner. On this basis, we propose a GPU-accelerated and continuous-annealing-enhanced training pipeline for BIPNN. The pipeline enables BIPNN to optimize large-scale nonlinear terms in BIPs fully in parallel via straightforward gradient descent, thus significantly reducing the training cost while ensuring the generation of discrete, high-quality solutions. Extensive experiments on synthetic and real-world datasets highlight the superiority of our approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。