BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks
Journal:
arXiv
Published Date:
May 27, 2025
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.
