Research map / Learning theory and algorithms / Combinatorial and search optimization
BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BIPNN, an unsupervised HyperGNN solver that reformulates nonlinear binary integer programs into polynomial unconstrained losses (via hypergraph incidence matrices, GPU-parallel evaluation, and continuous relaxation annealing) and outperforms SCIP and Tabu on large instances and hypergraph max-cut.
Problem
Solving large-scale nonlinear binary integer programming (BIP) problems, where linearization-based branch-and-cut solvers like SCIP suffer exponential growth in auxiliary variables and cost, while existing neural ILP solvers do not handle nonlinearities.
Approach
Map polynomial BIP objectives one-to-one onto hypergraph structures, reformulate constraints and nonlinear univariate/multivariate terms into polynomial penalty losses, and train a two-layer HGNN+ unsupervised with a GPU-parallel PUBO loss and a continuous relaxation annealing penalty to output near-binary solutions.
Key results
- On max-cut, BIPNN obtains the best cut on 5 of 8 datasets (e.g., Cora 1,384 vs SCIP 1,215 and Tabu 1,360), while SCIP wins on BAT, DBLP, and CiteSeer.
- BIPNN's solving time grows roughly linearly with problem size whereas SCIP's grows exponentially; BIPNN outperforms SCIP's solution quality beyond 2,500 variables for degree 4 and beyond 1,000 vertices for degree 6 under a 1-hour limit.
- BIPNN matches Tabu at around 1,000 variables and significantly outperforms it beyond 2,500 variables.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BIPNN instead of SCIP | BIPNN · EAT | cuts: 3,849 -> 3,978 | Helped |
| Use BIPNN instead of SCIP | BIPNN · UAT | cuts: 7,899 -> 8,407 | Helped |
| Use BIPNN instead of SCIP | BIPNN · Primary | cuts: 7,603 -> 8,509 | Helped |
| Use BIPNN instead of SCIP | BIPNN · High | cuts: 4,599 -> 5,216 | Helped |
| Use BIPNN instead of SCIP | BIPNN · Cora | cuts: 1,215 -> 1,384 | Helped |
| Use BIPNN instead of SCIP | BIPNN · BAT | cuts: 655 -> 651 | Hurt |
| Use BIPNN instead of SCIP | BIPNN · DBLP | cuts: 2,869 -> 2,801 | Hurt |
| Use BIPNN instead of SCIP | BIPNN · CiteSeer | cuts: 3,960 -> 3,852 | Hurt |
| Use BIPNN instead of Tabu | BIPNN · EAT | cuts: 3,972 -> 3,978 | Helped |
| Use BIPNN instead of Tabu | BIPNN · Primary | cuts: 8,500 -> 8,509 | Helped |
| Use BIPNN instead of Tabu | BIPNN · High | cuts: 5,160 -> 5,216 | Helped |
| Use BIPNN instead of Tabu | BIPNN · Cora | cuts: 1,360 -> 1,384 | Helped |
Surprising findings
- SCIP achieves better cut values than BIPNN on three of the eight graph/hypergraph max-cut datasets (BAT, DBLP, CiteSeer).
Limitations
- Polynomial reformulation grows exponentially with the number of variables in a nonlinear term (2^|S| evaluations) and hyperedge count can explode for high degree d.
- Feasibility of constrained problems is only checked during training or by post-hoc sampling, with no formal guarantee.
- SCIP still outperforms BIPNN on some real-world graph max-cut datasets.
Experimental setup
Datasets: DHG-generated synthetic hypergraphs BAT EAT UAT DBLP CiteSeer Primary High Cora
Benchmarks: synthetic BIP instances hypergraph max-cut on BAT, EAT, UAT, DBLP, CiteSeer, Primary, High, Cora
Metrics: solving time solution ratio to SCIP number of cuts training time
Baselines: SCIP Tabu search MIP-GNN
Builds on: HGNN+ continuous relaxation annealing penalty methods
Closest papers by meaning
- MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers (AAAI 2022 · similarity 0.90)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.87)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.87)
- Rethinking the Capacity of Graph Neural Networks for Branching Strategy (NeurIPS 2024 · similarity 0.87)
- Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming (ICLR 2025 · similarity 0.86)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.