Abstract
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.
Abstract (translated)
二进制（0-1）整数规划（BIP）在需要离散决策的科学领域中至关重要。随着人工智能计算的发展，最近的研究工作探索了基于神经网络的求解器来解决整数线性规划（ILP）问题。然而，这些方法在应对非线性挑战时缺乏可扩展性。为了处理非线性问题，最先进的分支切割法利用线性松弛技术，导致辅助变量数量呈指数级增长，并且计算限制严重。 为克服这一局限，我们提出了BIPNN（二进制整数规划神经网络），这是一种无监督学习框架，通过超图神经网络（HyperGNN）解决非线性的BIP问题。具体而言，BIPNN将受约束、离散和包含非线性项（如正弦、对数、指数函数）的BIP优化问题转化为无约束、可微分和多项式形式的目标函数。这种转化基于这样一个观察：即多项式BIP目标与超图结构之间存在精确的一一对应关系，这使得能够通过端到端的方式训练HyperGNN来解决BIP问题。 在此基础上，我们提出了一种GPU加速并结合连续退火增强的BIPNN训练流程。该流程使BIPNN能够在大规模非线性项中完全平行地优化整数规划（BIP）中的多项式损失函数，从而通过简单的梯度下降显著降低了训练成本，并且在确保生成离散、高质量解的同时提高了效率。 广泛的合成和现实世界数据集上的实验显示了我们方法的优越性能。
URL
https://arxiv.org/abs/2505.20997
