BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks
Authors: Sen Bai
Chunqi Yang
Xin Bai
Xin Zhang
Zhengang Jiang
Venue: NeurIPS 2025 poster ()
Keywords: binary integer program
hypergraph neural network
nonlinear integer programming
Primary area: machine_learning_for_sciences
TL;DR: This paper proposes a neural network-based binary integer programming solver.

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 solver 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, an unsupervised learning framework to solve BIP problems via hypergraph neural networks (HyperGNN). Specifically, (i) 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, (ii) 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.

BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks
Sen Bai* baisen@cust.edu edw.eeuuusteuuu.....m cn
Chunqi Yang* Sangchunqi@maiss cust. edu. cn
Xin Bait
baixinbs@163.ccm com com
Xin Zhang zhangxin@cust enu.cn
Zhengang Jiang" j jingzhengang@oust.cco
Abstract
Binary (0-1) integer programming (BIP) is pivotal in scientific domains requiring discrete decision-making. As the advance of Al 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 ex- ponential growth in auxiliary variables and severe computation limitations. To overcome these limitations, propose BIPNN (Binary Integer Programming Neural Network), an unsupervised learning framework to solve nonlinear BIP problems via hypergraph neural networks (HyperGNN). Specifically, (I) BIPNN reformulates BIPs-constrained discrete, and nonlinear (sin, log, exp) optimization problems-inte into unconstrained, differentiable, and polynomial loss functions. The reformulation stems from the observation of precise one-to-one mapping between polynomial BIP objectives and hypergraph structures, enabling the unsupervised training of HyperGNN to optimize BIP problems an end-to-end manner. On this basis, (II) we propose a GPU-accelerated and matinnous-annealing--oo 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, higl-quality solutions. Extensive experiments on synthetic and real-world datasets highlight the superiority of our approach.
Introduction
For decades, binary integer programming (BIP) a powerful mathematical tool characterized by discrete binary decision variables (0 or 1)-is of critical importance in numerous domains, such as operational optimization [T] 2, 31 quantum computing 4 [ 6). computational biology [77 [), materials science and computational chemistry ( [00. However, BIP is generally known to be NP-complete [11, making large-scale BIP instances computationally intractable.
Along with Al computing shines in scientific discovery, the potential of neural network-basee IP solvers has emerged recent years. To address integer linear programming (ILP) problems, MIP-GNN [2] leverages graph neural networks (GNN) improve the performance. Another GNN&GBDT-gguded framework [33] for large-scale ILP problems can save up 99% of running time
'School Computer Science and Technology, Changchun University Science and Technology.
Huawei Technologies Co. Ltd.
I *Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The BIPNN Framework:
Neural Network based Oplimizer
BIP Problem
Unconstrained Reformulation
min
-4 -inn(x))++ +X,
PUBO Loss
min
0.8451xx xx 2xx 2x
stt.
2X +3x <5
X E 1-1,2,34
Training to optimize
Hypergraph
Converge
Polynomial Reformulation min
X
Solutions
0.8451xXx Xx 2%,
x
HyperGNN NN
x2
s.t. +1.7183x, +3x,,
el
X
X E (01) 1=12,344
V/
X
Training Workllow:
Neural Network based Optimizer
Relaxation X =[01]
PUBO Loss
Random T Tensors
HyperGNN
Output
min OJUBO ~ 29xx Σ OUXZY +...
Sigmoid
GPU accelerated PUBO loss
Ampeliy
min OPURO ColM o H- (1- HIP dxx
Example: GPU acoelerated PUBO loss
Output X:
Incidence M aalix H:
X
H:
H
H
Q':
9
0
6
Q
6
eg
4
4
9
02
0
Q
9
6
6
0
0.6
0.6
0
0
0.6
0
0
1
0.6
0.6
0.6
0.2
1
0
0.2
0
1
0
0.2
0.2
0.3
0.3
0.3
0.12
0.04
0.1
0.1
0.1
COlM
Figure 1: The BIPNN framework. As shown in and d, BIPNN's ' hypergraph modeling (Sec. 3.1 stems from the key observation that when variables are treated as nodes, any monomial with coefficient can be represented as hyperedge, while polynomials can be expressed through hypergraphs and vice versa.
in achieving the same solution quality SCIP [14], leading IP solver. However, these neural network-based II.P solvers lack scalability for nonlinear BIPs (please refer to Appendix A).
To handle nonlinearities, state-of-the-art Branch-and-Cur solvers (e.g., SCIP [15] rely on linear relaxation, which introduces a number of auxiliary variables. Once linearized, these problems are solved using linear programming (LP) solvers (e.g., the Simplex method") Consequently, large-scale nonlinear BIPs often suffer from prohibitive computational costs. As BIP solvers continue evolve, linearization remains indispensable for making nonlinearities more tractable for BIP solvers.
These limitations motivate us to develop a streamlined and general-purpose BIP solver advance the state of the art. To profoundly adapt to real-world applications, our work grapples with chal- lenges arising from neural networks' unique characteristics beyond linearization-bat methods, as summarized below:
Challenge 1. Meticulously modeling nonlinear terms in BIP objectives and constraints:
Challenge 2. Utilizing GPU's parallel computing capability.
To this end, in this work we propose BIPNN (Binary Integer Programming Neural Network), an unsupervised BIP solver that bridges the gap between nonlinear BIP and deep neural networks. Our overarching idea stems from the observation of one-to-one mapping correspondence between polynomial BIP objectives and hypergraph structures (upper right of Fig. I]. As depicted in Fig. our framework consists of three phases:
'To be precise, the Simplex method is designed to solve linear programming (LP) problems in polynomial time, meaning they belong to the class [16].

---

1) In the first phase, we employ broadly applicable penalty term method to convert constrained BIP problems into polynomial unconstrained binary optimization (PUBQ") formalism. To handle exponential and trigonometric terms, we propose a novel transformation to represent them in the form of polynomials. These refined polynomial objectives are adaptable to neural network-based solvers when applied as loss functions.
2) In the second phase, we leverage hypergraph neural networks (HyperGNN) to address Challenge capturing high-order correlations between binary decision variables, or in other words the polynomial terms in the refined PUBO objective. By applying relaxation strategy to the PUBO objective to generate differentiable loss function with which we train the HyperGNN in an unsupervised manner.
3) Nevertheless, when train these HyperGNNs to minimize the PUBO objectives, encounter severe obstacles of low computational efficiency in these polynomial losses with numerous variables. In the third phase, leveraging GPUs, further propose algorithm to address Challenge 2 via matrix operations on the incidence matrices of hypergraphs.
In summary, we contribute:
1) BIPNN, an unsupervised HyperGNN- solver that allows learning approximate BIP solutions in an end-to-end differentiable way with strong empirical performance.
2) An empirical study of the performance of BIPNN synthetic and real-world data, demonstrating that unsupervised neural network solvers outperform classic BIP solvers such as Gurobi and SCIP in tackling large-scale nonlinear BIP problems.
3) Large-scale nonlinear optimization has long been challenging due to its inherent complexity and scalability issues. We advance this field by employing several nonlinearity modeling methods for BIP, including the polynomial reformulation and unconstrained reformulation. These methods provide instructive guidance for unsupervised neural network-based solvers.
2 Notations and Definitions
In the following, we will formulate the BIP problem and articulate the definition of hypergraphs.
Definition 1 (Formulation of BIP). Nonlinear BIP is an optimization problem where the decision variables (I1, 22, ... Im) are restricted to binary values (0 1), and the objective function OBI or constraints (or both) are nonlinear. Below is the general formulation.
min
OBIP~
f(x)
S. t.
(x) < 0 for all k: = 1, ,,,,K 1 = 1,2...., (x) = 0 for all
I, E 1} for all i= 1.2.....
where fxx), gl (x) and (x) are nonlinear functions of the decision variables x.
Definition 2 (Hypergraph). A hypergraph is defined by G EV,E), where V V= ( U2 ..., vv stands for a set of vertices and = {e1, G2 .2..... e } denotes a set of hyperedges. Each hyperedge ej E is subset of V. hypergraph G can be represented by the incidence matrix (Fig. at the bottom) H (0, (0, where H.j if Cj. or otherwise H 0.
3 BIPNN: Hyper Optimizer for PUBO-formulate BIP
For easier comprehension of our approach, in this section we first elaborate how to solve an uncon- strained, PUBO-formulated BIP problem as depicted in 2 Then, in Sec. 4 we will show how to transform general BIP problem with constraints and nonlinear terms into PCBO formalism.
3.1 Modeling PUBO-formulated BIPs via Hypergraphs
BIPNN employs a HyperrGNN-baseee optimizer (upper right of Fig. 1 to solve formulatdd BIP problems. Inspired by the binary characteristic of variables, we can reformulate general BIPs as
'The mathematical formulation PUBO is well known in quantum computing, for modeling complex opti- mization problems in way quantum computers may solve efficiently.
3

---

PUBO vector: 01.
Incidence matrix H;
G
2
PUBO O. D20 D.TON
Care DAG.E
1
e
9 x, 62
2 x
e4 xx
X 0
0
Polynomial terms:
6s
X4 0
Figure 2: Modeling PUBO-formulated BIPs via hypergraphs.
PUBO problems through the polynomial reformulation in Sec 4.1 and unconstrained reformulation in Sec A PUBO problem is to optimize the cost function:
OPUBO = EQi
Qias + Eijaae +
E $J..
QiAAzZZz +...
1.3
where x, E [(,01] are binary descision variables and the set all decision variables is denoted by (21, ( "", , ). As shown in Fig. 2 for ease of representation, PUBO objective OPUBO with n terms can be decomposed into two components: the PUBO vector Q = [Q1, Q2. Qn) and linear or polynomial terms such 24, Iy 22 In this way, we discover multi- variale interactions in OPUBO can be modeled as a hypergraph G = E), where |E| = n, and each hyperedge E E encodes single descision variable x; polynomial term such 24 ya
3.2 Neural Hetwork-basedd Optimizer
The training workflow of the neural network-based optimizer is illustrated at the bottom of Fig.
HyperGNN Architecture. Initially, for rUBn-franfformed hypergraph G = (V. E), HyperGNNs take the incidence matrix H of G and randomly initialized X()) E gmxd as inputs. Subscquently, BIPNN applies the sigmoid function to produce the output vector x T2, .mm. where I, [0, are the relaxation of decision variables E {0, The HyperGNN model operates as follows:
x (igmoid((yyeerrNNNHH... (())
where HyperGNN is multi-layer hypergraph convolutional network. HyperGNNs are graph-based deep learning architectures that generalize GNNs to operate on hypergraphs. These HyperGNN models includes HGNN+ [17], HyperGCN [18), UniGCN [19] (or UniGAT, UniSAGE, UniGIN). We have tested these models and observed that HGNN+ always outperformed other methods (refer to Appendix F.4 Thus in this work we use HGNN+ build BIPNN. The (-th convolutional layer of HGNN is built as below:
X = HW DJ x
HW
where (0) is the embedding matrix generated by the I-th convolutional layer. For a vertex e in the hypergraph, the degree is defined dog(v;) DeSEE Hiy. Similarly, the degree of an edge ej E E defined as deg(e,) Euev Hij- D, and D, are used to denote the diagonal matrices of the vertex degrees and edge degrees, respectively. W diag(lei). .... !llay) can be regarded as the weight of hyperedges. The parameter (())
is learned during training.
Training to Optimize. As an unsupervised learning model, BIPNN relaxes the PUBO objective OPUBO into differentiable loss function and trains optimize it. Specifically, OPUbo can be expressed by the output x and the incidence matrix as depicted in Fig. [ We aim to find the optimal solution x arginiOOPRRO (x, H). As training progresses, x; x will gradually converge to binary solutions.
eeU-accele Training. For a large-scale BIP problem, numerous polynomial terms in OPUBO lead to a high computational cost. To address this, an intuitive idea is to leverage GPU-supported matrix operations to accelerate training. However, PUBO problems lack straightforward matrix formulation. To this end, we propose GPU-accelerated PUBO objective as follows.
OPUBO ColM(x (B) H + T
(5)

---

where x is the output of HyperGNN, H is the incidence matrix, and Q = [Q1, Q2. Qn1 is the PUBO vector. More concretely, x ((B) H denotes the element-wise Hadamard product with broadcasting between m-dimennional vector x and matrix H E R We add 1- / on x (BB) H to fill zero-valued elements with 1. Based on this operation, we use the column-wise multiplication denoted by ColM on the first dimension of the matrix obtained by x @ H + (1 H). Through the ColM operation we obtain an n-dimensional vector, of which each element represents a polynomial term in OPUBO- The final loss function is computed by scaling each polynomial term with its respective coefficient Qi The detailed explanation illustrated in Fig.
Eq. transforms the computation of large-scale polynomials into efficient matrix operations, It leverages Pyprocs- broadcasting mechanisms to distribute the vector of decision variables across each monomial (hyperedge), enabling parallel computation.
Time Complexity Analysis. For R" Q R R and H IR*"" the time complexity of Eq. is O(m X n). For GPU-accelerated training. element- wisen operations such as Hadamard product are fully parallelizable. Column-wite product over m leads to time complexity O(logm). Thus, the theoretical best GPU time complexity is Ollggm). Utilizing T cores, the realistic GPU time complexity is O mxn
Annealing Strategy. To achieve unsupervised learning, BIPNN relaxes PUBO problems into continuous space. The differentiable relaxation of discrete decision variables sometimes leads to continuous solutions T, E [o, IJ. To address this, we employ the continuous relaxation annealing (CRA) (20) method. Specifically. BIPNN uses the following loss function: OPUBO = ColM @ H (1 (((1--))) H))Q²= + o(x), where o(x) = y Σi= (1- (2z, - 1)a) is the penalty term, y controls the penalty strength and is an even integer. We initialize < 0 and gradually increase it to a positive value training progresses. The annealing strategy enhances the performance of BIPNN in three aspects, (i) In the high-temperature phase (y 0), it smooths the HyperGNN, preventing it from getting trapped in local optima: (ii) In the wwwteemperature phase (7 > 0), it enforces the discreteness of solutions; (iii) It effectively accelerates the training process.
4 BIPNN: Polynomial & Unconstrained Reformulation of BIP
In this section, we explain how to reformulate nonlinear BIPs as unconstrained and polynomial optimization problems, which are compatible with our neural network-based optimizer.
4.1 Polynomial Reformulation of BIP
Our approach is inspired by the observation that for any binary variable, a nonlinear term such as ex can be exactly fitted by polynomial equivalent h(x) ax + b, such that h(r) = e for E 10, That is, h(x)= = (c - 1)xr +1, where h(0) 1 and h(1) = e. To handle univariate nonlinearities, including trigonometric, logarithmic, and exponential terms (e.g., sinz, logı, and e"), we have the following transformation: h((x) = (h(1) - h())) + h()). For multivariate terms such as e= and sin(x,,;)) where æ;Kú E {0, }.. we can perform the transformation as follows: WIIIes xx) = (h(1) ((0) Ih 24 + I(O)..
BIPNN employs more general method to handle more intricate multivariate nonlinear terms (such as sin(x; + 2,))). For a set of binary decision variables T2,42, .., non-linear function 1(11, 12, ) can be transformed into the polynomial forms as follows.
h(11, I22 Lm))
Σ
CS III a
(6)
SC(1.2......
iES
By setting up a system of equations based on all possible combinations of 3 22, ..., Tm. we can de- termine the coefficients es to precisely fit h( 42, ..., Im) by leveraging simple inclusion-cxclusion principle (refer to Appendix D.I as below.
CS = Σ (-1))S--T)((T)
TES
where /(T) represents the function value when the variables in the subset T are 1 and the others 0. For each subset S, it needs to calculate 21 values of fT)).
5

---

As an example, we have sin(21 + r2) = 0.84152; + 0.841522 - 0.773721 A toy example of sin + I2 + 23) is illustrated in Appendix D.1 To be noticed, polynomial reformulation of all nonlinear terms in BIP objective is not necessary. If the transformation becomes overly complex, we may opt to retain the original nonlinear term and directly incorporate as part of the loss function of HyperGNN.
4.2 Unconstrained Reformulation of BIP
We propose a novel penalty method to transform the constrained BIP problem into an unconstrained form. In penalty methods 22,,,, unconstrained reformulation is achieved by adding "penalty terms" to the objective function that penalize violations of constraints. must be designed such that it equals 0 if and only if the constraint is satisfied, and takes positive value otherwise. Specifically, given a BIP problem in Eq. ! for inequality constraints ga (x) S 0, we have penalty terms (x( = A (max (0, gu (x)))² for equality constraints q: O, we have penalty terms Qi(x)= = μ4 (g:(x)) where AE, 14 are sufficiently large penalty coefficients (For the selection of proper values of AR. 14t, please refer to Appendix(C] (C). By combining all terms into single
well-constructed penalty term
objective function, we have an unconstrained BIP objective:
min OBP = f(x) A (max (0,
+ Σ m (x(x)))
As part of the loss function of BIPNN, OBI must be differentiable enable gradient-based op- timization. However, max (0, Sb (x)) is not continuously differentiable function, thus finding an appropriate penalty term is crucial. We propose two methods to address this issue:
1) ReLU-based Penalty. We can use ReLU((g (x)) = (max(0, gk (x)))² to handle constraints. This is general method for a large number of variables I; in a constraint gl (x).
2) Polynomial Penalty. In the following, we present an algorithm to construct polynomial penalty terms with 2 time complexity for gı (x), where A is the number of variables in constraint (x).
For binary variables, do there exist polynomial penalty terms that correspond BIP constraints? To answer this question, we have the following discussion. For æ + 2x² - 2 < O, we observe that the violating subset {=1 1, 22 = ]} corresponds polynomial penalty term ((x)22)) For another constraint + 3r- 2 < O, the violating subsets {I1 = 0, 22 = 1} and {x1 1, 22 = 1} correspond to the polynomial penalty term A(z2 + x1 or Azz Through an in-depth analysis, we propose novel method to transform nonlinear BIP constraints into polynomial penalty terms. To handle an inequality constraint g(x) < O for the BIP problem Eq. 1 our method consists of three steps (to see toy example, refer to Appendix D.2):
(i) Initially, express the constraint g(x)
s
0 boolean indicator function:
+(x)
{1 if g(x) (violation) then define minimal violation subsets as the smallest variable com- (0 otherwise (feasible) binations causing constraint violations:
V { S (I, (xx) when x; Vi E S and x, = ovj $
(9)
each S V cannot be reduced further without eliminating the violation.
(ii) Generate a penalty term for each minimal violation subset S E V:
P(x)=
> x
(10)
SEVIES
where À is the penalty coefficient.
(iii) Combine each term into the BIP objective function:
min OBIP = f(x) + P(x)
(11)
In the worst case, when an enumeration method used in step (i), requires calculating 2 subsets, where A is the number of variables in constraint gxx). Nevertheless, in most real-world problems

---

e
PUBO Loss
min
2x +2x + +2x +x+ 3xxx - Xx
- X
-x
X
Q
X2
training to optimize
max cut problem
hypergraph modeling
BIPNN
Figure 3: To solve the hypergraph max-cut problem, BIPNN generates new hypergraph structure. However, both of these hypergraphs can be utilized for training the HyperGNN model.
(e.g. max-cut, and maximal independent set or MIS) involving graphs, the variables associated with each constraint often exhibit locality.
The polynomial penalty method facilitates to incorporate penalty terms to PUBO objectives and use GPU-accelerated training pipeline to solve BIPs. As far as we know, only few number of constraint/penalty pairs [22] associated have been identified in existing literature. Our work significantly expands the potential application domains of the penalty method.
Discussion
Feasible Solutions. Firstly, a PUBO problem always has feasible solutions. The feasible set is the entire space of binary variable combinations, since there are no constraints to exclude any combination. Every possible binary assignment z; E {0, 1} is inherently feasible. Secondly, the feasibility of nonlinear BIP problem depends on the constraint compatibiliyy-iiie
there exists at least one 1) 1) that satisfies all nonlinear constraints simultancously. In BIPNN, we determine the existence of feasible solutions through (i) Training-phant feasibility check: if all penalty terms (c.g.. constraint violations) converge to zero during training, feasible solutions exist; otherwise, the problem is infeasible.
binary variable assignment E
(ii) Post-training verification: we sample candidate solutions from the trained model and explicitly verify whether they satisfy all constraints.
The Effectiveness BIPNN's s Hypergraph Generation Mechanism. As depicted in Fig. 3 when BIPNN is applied to solve combinatorial optimization (CO) problems hypergraphs, it generates an alternative hypergraph structure. However, both the hypergraphs can used as the input of BIPNN. A critical question arises: which type of hypergraph structure achieves better performance when applied to HyperGNN? The main difference between these two hypergraphs is that the hypergraph generated by BIPNN breaks down the original hypergraph's 's high-order hyperedges into numerous low-order ones. We argue that BIPNN training with the original hypergraph structure is more computationally efficiency, while BIPNN- hypergraph structure leads to more optimal solutions. In Sec. 6.3 we will empirically compare the solution quality of both methods.
6 Experimental Results
In this section, we describe our empirical experiments on BIPNN and baseline optimization tools. Our source codes can be obtained on GitHut
Benchmarks. evaluate BIPNN on BIP problems with diverse scales, the datasets are generated using DHG library To evaluate the quality of solutions and computational efficiency of BIPNN, datasets of varying scales are generated in three steps: Initially, DHG library is applied to generate hypergraph structures (where EE| 2)V)). Subsequently, a random coefficient is assigned to each hyperedge (representing a polynomial term) to generate PUBO objective functions. Thereafter, several constraints (penalty terms) were randomly incorporated into the PUBO objectives. To demonstrate the effectiveness of BIPNN on real-world settings, we also conduct experiments on the hypergraph max-cut problem (refer to Appendix E), a well-known BIP problem benchmark. Moreover, conduct experiments on aublicly-available hypergraph datasets (refer to Appendix F.I
Integer-Programming via- via-Hypergrapph
Neural-Networks httg:///leehhppeemmmooooaaaaooes

---

1200
3600
(seconds)
BIPNN SCIP
Time (soconds)
BIPNN
Solutions
SCIP
1.05
800
Gurobi
2400
Gurobi
1.00
0.95
400
1200
0.90
BIPNN
SCIP
0.75
1200
2400
3000
600
1200 1800 2400
3000
1000
2000
3000
4000
Number of Vartices
Number of Vertices
Number of Vertices
(a) d d= 4.
(b) = 6.
1.05
1.12
Ratio Solutions
1.20
1.28
Ratio Solutions
1.00
Ratio of Solutions
1.04
1.12
0.95
0.96
0.88
BIPNN
0.90
BIPNN Gurobi
BIPNN
0.80
0.88
SCIP
0.85
0.80
Gurobi
1000
2000
3000
1000 5000
1000
2000
3000
5000
Number of Vertices
Number of Vertices
Number of Vertices
(d) d 6.
(e) d = 4.
(f) d 6.
Figure 4: Comparison of BIPNN and BIP solvers such as Gurobi and SCIP. the degree of polynomial terms in BIP objective functions. (a)()) show the solving time required for BIPNN, SCIP and Gurobi to obtain the same solution. (c)(d) show the ratio of the solutions of BIPNN to SCIP; (f) illustrate the ratio of the solutions of BIPNN to Gurobi; Runtime is restricted to half hour.
Baseline Methods. In our experiments, the baseline methods include optimization techniques and tools such Gurob SCIP 14 (refer to Appendix Ap. Tabu search 23
Implementation Details. Experiments are conducted on an Intel Core 19-12900K CPU with 24 cores, and an NVIDIA GeForce RTX 3090 GPU with 24 G of memory. We adopt two-layer HGNN+ [17 as the HyperGNN model for the experiments.
6.1 Comparison with Linearization-basel BIP Solvers
Gurobi and SCIP are exact solvers based on the branch-and-cut algorithm. Theoretically, given sufficient time and computational resources, they guarantee exact solutions. However, for large- scale problems, due to time constraints, Gurobi and SCIP may terminate prematurely and return approximate solutions. To conduct the experiment, we generate a specific BIP instance for each size of variables. Specifically, for a BIPNN- hypergraph, the number of vertices (variables) [V] ranges from 200 to 3000. The degrees of vertices are set to (Fig. 4a) and (Fig. 4b) respectively.
Fig. 4a and Fig. 4b show the comparison of the solving time for BIPNN, SCIP and Gurobi. We evaluate the solving time taken by BIPNN obtain the best approximate solution and the time required by SCIP and Gurobi to find the same solution. Experimental results demonstrate that the solving time of BIPNN grows linearly and slowly with increasing problem size, while SCIP and Gurobi's solving time exhibits exponential growth. This trend becomes more pronounced when the degree of polynomial terms is 6.
Moreover, we impose half an hour time limit and evaluate the solution quality of BIPNN, SCIP and Gurobi across varying scales of BIP instances. Fig. 4c
4d
4e
4f show the comparative ratio
of solutions obtained by BIPNN, SCIP and Gurobi. The comparative ratio is defined as QHENN O Lanase
where BIPNN is the solution obtained by BIPNN, and O is the solution obtained by SCIP and Gurobi. Experimental results demonstrate that BIPNN starts outperforming SCIP when the number of variables exceeds 2, 500 when d = 4. As the problem size increases, BIPNN's solutions increasingly outperform SCIP's solutions. For 6, BIPNN outperforms SCIP when the number of vertices exceeds 1, 000. The results Gurobi show pattern similar to SCIP. The number of variables required for BIPNN to outperform Gurobi is 4, 300 when = 4. For d = 6, BIPNN outperforms Gurobi when the number of vertices exceeds 3, 500.
"attps//www.gurbbi.com

---

Table 1:
The solutions of graph/hypergraph max-eut problems.
Method
BAT
EAT
UAT
DBLP
CiteSeer
AmzPhoto
Primary
High
Cora
PubMed
Gurobi
655
3,997
8,431
2,869
3,960
72,461
8,448
5,195
1,400
7,226
SCIP
655
3,849
7,899
2,869
3,960
59,258
7,603
4,599
1,215
7,185
Tabu
652
3,970
8,402
2,710
3,717
71,970
8,500
5.160
1,360
6,868
BIPNN
653
3,997
8,463
2,847
3,944
83,446
8,516
5,252
1.397
7,188
40
Original toperpaaph hypengephy
Original hyppeggeph
2000
RIPNN' hepergmai
Original hypehanph BEPNNN, crngraph
Namveer of Clt
Original by praph
Tune (ocozad))
1500
1500
BIPNN Sargraph
25
Number
1000
2000
20
50
500
500
1000 2000
500
1500
500
1000 1500 Nisther Vartiess (c) = 4.
1000 2000
Namberr Vartizes
Numher of Vertiess
Number Variles
(a) d
(b) d = 6.
(d) d = 6.
Figure 5: Comparison of the quality of solutions and time efficiency of BIPNN when it applys its generated hypergraph structure or the original hypergraph structure solve hypergraph max-cut problems. d is the degree of polynomial terms in BIP objective functions. (a)(b) show the numbers of cuts; (d) show the solving time.
Additional experimental results on large-scale BIP problems can be found in Appendix F2 The performance of BIPNN compared with Tabu search illustrated in Appendix F3
6.2 Comparison on Real-world Datasets
We compare BIPNN against baseline methods on real-world graph and hypergraph datasets, in- cluding BAT, EAT, UAT, DBLP, CiteSeer, AmzPhoto, Primary, High, Cora and PubMed (refer to Graph datasets include BAT, EAT, UAT, DBLP, CiteSeer, and AmzPhoto. Hypergraph
Appendix F. datasets include Primary, High, Cora, and PubMed. Graph and hypergraph max-eut problems selected as the BIP problem benchmarks. We impose hour time limit and evaluate the number of cuts obtained by Gurobi, SCIP, Tabu, and BIPNN.
As depicted Tab. D Gurobi outperforms SCIP and Tabu on all graph and hypergraph datasets. Moreover, experimental results show that the performance of Gurobi and BIPNN varies across different datasets. Gurobi achieved the best performance on four graph datasets and two hypergraph datasets, while BIPNN achieved the best performance on three graph datasets and two hypergraph datasets.
Comparative Analysis on Hypergraph Generation Mechanism
In Sec. 5 and Fig. we propose to evaluate the effectiveness of BIPNN's hypergraph generation mechanism by comparing the effects of its generated hypergraph structures against the original hypergraph structures in hypergraph CO problem. In this section, we select hypergraph max-cut as benchmark and conduct experiments to evaluate the performance hypergraph structures. Experimental results are depicted in Fig. 5 The number of variables ranges from 100 to 2000. The degrees of polynomial terms d are set to d = 4 and d = 6 respectively, We perform 10 tests each time and record the average value of the cut numbers.
BIPNN under both of the
As illustrated in Fig. 5a and Fig. [5b] the hypergraph structure generated by BIPNN can identify more cuts in comparison. However, as depicted in Fig. and Fig. [d when the parameter d is larger, the number of hyperedges (polynomial terms in PUBO objectives) in the hypergraph structure generated by BIPNN increases sharply, leading to significantly higher computational costs. The results align with the theoretical analysis we presented in Sec. 5 Unlike conventional machine learning tasks (e.g., node classification), we hypothesize that the hypergraph structure for BIPNN should be related to the loss function. Thus HyperGNNNs energy flow directs each polynomial term along proper gradient paths.

---

6.4 Ablation Study
GPU Acceleration. The superior time efficiency BIPNN is primarily attributed to the -PU-accelert algorithm employed computing large-scale PUBO loss functions. Fig. 6 shows comparison of the training times for BIPNN with or without the GPU-accelerated algorithm. We evaluate the training time of BIPNN on the hypergraph max-cut problem. The number of
250
GPU-aceleration
CPU-only
Time (sccoads)
200
150
variables ranges from 200 1000. The degree of polynomial terms is set to 4.
100
We train BIPNN for fixed number of 1000 epochs. As Fig. il lustrates, when GPU acceleration is applied to compute the PUBO loss function, the training time does not exhibit significant growth with an increasing number of variables. In contrast, without GPU acceleration, the training time increases rapidly as the number of variables rises.
50
200
600
Number of Vartices
Figure Comparison of the training time for BIPNN with or without GPU accelerated algo- rithm for PUBO losses.
Annealing Strategy. We validate the effectiveness of the anneal- ing strategy of BIPNN on the hypergraph max-cut problem. The experiments are conducted on Cora with 1, 1,330 vertices. The met- rics include the number of cuts and discreteness of variables. The penalty strength is set to 2.5 initially and its value gradually increased during training. The value reaches 0 after 500 epochs and continued to increase thereafter.
As illustrated in Fig. 7 the annealing strategy ensures BIPNN to get better solutions while guaranteeing all variables to converge discrete values. It demonstrates that negative values enable BIPNN to escape local optima, thereby discovering better solu- tions. Moreover, when y is positive values, it facilitates the convergence of variables toward discrete values.
Namber Contergeni Vertioos Cute
1000
800
Namber
With arnellng stritg snncaling strslggy
7 Conclusion
400
Namthe of convergal vartinn anolligg
This work proposes BIPNN, novel neural network solver for non- linear BIP problems. It reformulates nonlinear BIPs into PUBO cost functions, which correspond to hypergraph structures. On this basis, these PUBO cost functions are used as loss functions for HyperGNNs, enabling the model to solve BIPs an unsu- pervised training manner. Compared with existing BIP solvers (e.g., Gurobi, SCIP) that rely on linearization, BIPNN reduces the training cost by optimizing nonlinear BIPs via straightforward gradient descent. Empirical results demonstrate that BIPNN achieves state-of-the-ant performance in learning approximate solutions for large-scale BIP problems.
200
annzaling eisiagy
2000
Fpech
Figure 7: Quality and discrete- ness of solutions with or without the annealing strategy.
Acknowledgments and Disclosure of Funding
This work is sponsored by the Natural Science Foundation of Jilin Province under grants 20240101349JC, National Natural Science Foundation of China under grants 82472118.
10

---

References
[1] Yan Qiao, Yanjun Lu, Jie Li, Siwei Zhang, Naiqi Wu, and Bin Liu. An efficient binary integer programming model for residency time-constrained cluster tools with chamber cleaning requirements. IEEE Transactions on Automation Science and Engineering, 19(3):1557-1771, 2021.
[2] Theodore P Papalexopoulos, Christian Tjandraatmadja, Ross Anderson, Juan Pablo Vielma, and David Belanger. Constrained discrete black-box optimization using mixed-integer programming. In International Conference on Machine Learning, pages 17295-1723 17322. PMLR, 2022.
[3] Libin Wang. Han Hu, Qisen Shang, Haowei Zeng, and Qing Zhu. Structuredmesh: 3-d structured optimization of façade components on photogrammetric mesh models using binary integer programming. IEEE Transactions on Geoscience and Remote Sensing, 62:1-12, 2024.
[4] Giacomo Nannicini, Lev S Bishop, Oktay Günlük, and Petar Jurcevic. Optimal qubit assignment and routing via integer programming, ACM Transactions on Quantum Computing, 4(1):1-31, 2022.
[5] Akshay Ajagekar, Kumail Hamoud, and Fengqi You. Hybrid classical-quantung optimization techniques for solving mixed-integer programming problems in production scheduling. IEEE Transactions on Quantum Engineering, 3:1-16, 2022.
[6] Lei Fan and Zhu Han. Hybrid quantum-classical computing for future network optimization. IEEE Network, 36(5):72-76, 2022.
[7] Mercè Llabrés, Gabriel Riera, Francesc Rosselló, and Gabriel Valiente. Alignment of biological networks by integer linear programming: virus-host protein-protein interaction networks. BMC bioinformatics, 21(Suppl 6):434, 2020.
[8] Jianshen Zhu, Naveed Ahmed Azam, Fan Zhang. Aleksandar Shurbevski, Kazuya Haraguchi, Liang Zhao, Hiroshi Nagamochi, and Tatsuya Akutsu. A novel method for inferring chem- ical compounds with prescribed topological substructures based on integer programming. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 19(6)33233-322 3245, 2021.
[9] Vladimir V Gusev, Duncan Adamson, Argyrios Deligkas, Dmytro Antypov, Christopher M Collins, Piotr Krysta, Igor Potapov, George Darling, Matthew Dyer, Paul Spirakis, et al. Optimality guarantees for crystal structure prediction. Nature, 619(7968):68-72 2023.
[10] Georgia Stinchfield, Joshua C Morgan, Sakshi Naik, Lorenz T Biegler, John C Eslick, Clas Jacobson, David C Miller, John D Siirola, Miguel Zamarripa, Chen Zhang, al. A mixed integer linear programming approach for the design of chemical process families. Computers & Chemical Engineering, 183:108620, 2024.
[11] Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.
[12] Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10219-10227, 2022.
[13] Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, and Yu Jiang. Gnn&gbdt-gguide fast optimizing framework for large-scale integer programming. In International conference on machine learning. pages 00864-39878. PMLR, 2023.
[14] Stephen Maher, Matthias Miltenberger, João Pedro Pedroso, Daniel Rehfeldt, Robert Schwarz, and Felipe Serrano. PySCIPOpt: Mathematical programming in python with the SCIP opti- mization suite. Mathematical Software ICMS 20/6, pages 301-307. Springer International Publishing, 2016.
[15] Tobias Achterberg. Seip: solving constraint integer programs. Mathematical Programming Computation, 1:1-41, 2009.

---

[16] Narendra Karmarkar. A new polynomial-tine time algorithm for linear programmiigg In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302-311, 1984.
[17] Yue Gao, Yifan Feng. Shuyi Ji, and Rongrong Ji. Hgnn+: General hypergraph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(3):1181-319) 2022.
[18] Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. Hypergen: A new method for training graph convolutional networks on hypergraphs. Advances in neural information processing systems, 32, 2019.
[19] Jing Huang and Jie Yang. Unignn: unified framework for graph and hypergraph neural networks. In the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), 2021.
[20] Yuma Ichikawa. Controlling continuous relaxation for combinatorial optimization. Advances in Neural Information Processing Systems 37:779999477 2024.
[21] Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
[22] Fred Glover, Gary Kochenberger, Rick Hennig, and Yu Du. Quantum bridge analyties i: tutorial on formulating and using qubo models. Annals of Operations Research, 314(():141-183 2022.
[23] Fred Glover and Manuel Laguna. Tabu search. Springer, 1998.
[24] Zijie Geng, Jie Wang, Xijun Li, Fangzhou Zhu, Jianye Hao, Bin Li, and Feng Wu. Differen- tiable integer linear programming. In The Thirteenth International Conference on Learning Representations, 2025.
[25] Nasimeh Heydaribeni, Xinrui Zhan, Ruisi Zhang, Tina Eliassi-Rad and Farinaz Koushanfar. Distributed constrained combinatorial optimization leveraging hypergraph neural networks. Nature Machine Intelligence, pages 1-9, 2024.
[26] Zhixiao Xiong, Huigen Ye, Fangyu Zong. Yutong Zhang, Hua Xu, and Hongyan Wang. Neu- ralqp: A general hypergraph-base optimization framework for large-scale quadratically con- strained quadratic programs.
12

---

A Related works (Sec.
Gurobi & SCIP. Gurobi a commercial high- -eehrrrformance mathematical optimization solver. is widely used in industry and academia for solving large-scale linear programming (LP), mixed-integer linear programming (MILP), quadratic programming (QP), and mixed-integer quadratic programming (MIQP) problems. Gurobi is known for its speed. Moreover, starting with version 12.0, Gurobi supports nonlinear constraints. SCIP is a powerful open-source optimization solver. is primarily designed for solving MILP and nonlinear programs (MINLP) and is highly customizable. SCIP is widely used in academic research due to flexibility.
Table Categorizing several related neural network BTP solvers.
Method
SSueervised Unsupervised Linear Quadratic Polynomial
Hypergraph Modeling
BIPNN
objective & constraints
DifiLO 24
HypOp 25
constraints only constraints only
NeuralQP 26
MIP-GNN 12
In Tab. 2 we present recent neural network-basse -asse solvers for BIPs.
DifIILO [24]. DifilLO is an unsupervised method with performance that can exceed Gurobi and SCIP. Its methodology is the most similar that of BIPNN. However, DiffLLO is designed for linear BIPs, while BIPNN primarily addresses general nonlinear BIPs. DifiLLO employs bipartite graphs and GNNs to model constraints, whereas BIPNN utilizes HyperGNNS to represent nonlinear BIPs.
HypOp [25]. HypOp is also an unsupervised method. Compared with HypOp, BIPNN first discovers the mapping correspondence betweeen polynomials and hypergraph structures. Compared to linear and quadratic problems, the core challenge in solving nonlinear BIPs lies in leveraging GPU to accelerate training. BIPNN proposes computational framework specifically for this purpose. In contrast, HypOp utilizes distributed HyperGNN training, yet its hypergraph modeling solely targets constraints rather than objective functions, thus rendering HypOp inapplicable general BIPs.
They are supervised and designed for LP and QP problems. Supervised learning methods require precomputing vast amounts of labels [24]. Obtaining labels for nonlinear BIPs is challenging, since Gurobi and SCIP have higher computational overhead when solving nonlinear BIPs. Although MIP-GNN and NeuralQP demonstrate strong performance, they are specifically designed for LP and QP problems. In contrast, BIPNN is designed for solving more complex nonlinear BIP problems, making inherently difficult to match the performance of specialized LP and QP solvers.
MIP-GNN 12 & NeuralQP 26
Overall. BIPNN is proposed for general nonlinear BIPs, and it is fast. We believe BIPNN and DifIILO collectively address numerous limitations inherent penalty-based based deep learning methods for solving nonlinear BIP problems. In the future, they could potentially integrate commercial solvers (e.g., Gurobi, SCIP) to enhance large-scale BIP optimization. BIPNÑ's polynomial reformulation. unconstrained reformulation, and GPU-accelerated PUBO solver, may also potentially enhance other neural network-based BIP solvers.
B Discussion: supervised methods are not applicable to nonlinear BIPs (Sec. I
Table 3: SCIP's runtime when solving BIPs with polynomial objectives of degree 4.
Number of monomials
2400
3600
4800
6000
Linear Nonlinear
0.0037 s s
0.0047
0.0060
0,0073 s
350
553
1215
Most existing supervised methods are designed for II. and QP problems. They require precomputing labels via solvers like Gurobi and SCIP. However, Gurobi and SCIP exhibit exponentially slower
13

---

performance when solving general nonlinear BIPs compared to ILPs, making label acquisition practically infeasible. To verify this, we measured SCIP's runtime for BIPs with polynomial objectives of degree 4 (Tab. 3
Moreover, recent work DiffILOO [2 for linear BIPs reveals that supervised methods frequently produce infeasible solutions, due to the misalignment between training objectives (minimizing
prediction error) and inference objectives (generating high-quality feasible solutions).
C The selection of proper values of penalty factors (Sec. 4.2
In common Maximal Independent Set (MIS) problems, the penalty factor is typically fixed at 2. However, for general BIP problems, the choice of penalty factors critically impacts both constraint satisfaction and solution quality. This problem has been well-solved by DiffILO [24), unsupervised linear BIP solver. Specifically, we can use
A = Ho + 17.
(12)
where po is the initial value the penalty factor μt, 17 is the learning rate, and qi the value of the penalty term. We can initialize lio with a small value (e.g., 2 ~ 5) to broaden the model's I'' search space. The learning rate y should be experimentally tuned across different values (e.g., 0.001 1).
D Examples of polynomial reformulation and unconstrained reformulation
D.1 A toy example of the polynomial reformulation of BIP (Sec.
For sin(21 + 22 + rz), where 21, F2, 23 E {0, 1}, we can construct a polynomial to precisely fit the function, such that it matches sin(x1 + Ø2 + xz3) for all combinations of 21, 2i {0, 1]. For multiple binary variables, the polynomial can be generalized as:
P(1 P(11, xz) = a + 0222 + az33 + b12 + b1z0123 + b2g + c21 + d (13)
Based all possible combinations of æ 22, can set up the following equations:
1) When z1 = 0, 22 = 0, F3 = 0: P(O, 0, 0) = = (0) = 0. Thus, d=0. O.
2) When æ1 = 0, 0, 0, = 1: P(0, 0,
= sin (1) ~ 0.8415. Thus, a3 0.8415.
3) When æ1 0, 22222 1, 0: P(0, d2 sin (1) 0.8415. Thus, 02 0.8415.
4) When 21 22 0, 23 = 0: 0,), 01 = sin(1) ~ 0.8415. Thus, an 0.8415.
5) When æ = 0, .2 1, 1,43 = 1: 1,0, a2 + 03 + b23 = sin(2) ~ 0.9093.
Substituting d2 0.8415 and d3 0.8415: b23 -0.7737.
6) When z1 1, 22 0, 23 0,1, a1 + 03 + bis sin (2) 0.9093
Substituting d1 = 0.8415 and a3 = 0.8415: 613 = -0.7737.
7) When #1 1, 1, 233 = 0: 1,1,1,0) a1 + a2 + b12 = sin ~ 0.9093
Substituting 01 0.8415 and 02 0.8415: 212 0.7733
8) When + = 1, Ø2 = 1, 1: P(1,1,1) = + + ba sin(3) Rs 0.1411.
Substituting known values: c c -0.0623
Based on the above calculations, the polynomial is:
P(I1, 23) 0.8415(z; + + + 22) 0.7737(x)2) + 21 + F227a) 0.0623r, (14)
D.2 A toy example of the unconstrained reformulation of BIP (Sec.
For nonlinear constraint with exponential term g(x): 2x + の² 3x S 5, where æ 22; 23 {0, 1), can find the minimal violation subsets V based all possible combinations of x1, 22, Ø3.
14

---

1) When 0, 22 = 0, 23 = 0: g(x) = < 5, feasible.
2) When 21 0, 22 0,43
g(x) v 5, feasible.
3) When 21 = 0, 22 1, .T3 = g(x) = e S 5, feasible.
4) When 21 = 1, 0, X3 = 0: g(x = 3 - 5, feasible.
5) When # 0, 1, 1: g(x) S 5, feasible.
6) When 21 1, 0, .3 g(x) 6 2 5, violation.
7) When 21 = 1, = 1, 23 = 0: g(x) = e < 5, feasible.
8) When 1,22 1, = 1: g(x) = 5 + 2 5, violation (not minimal).
Identified minimal violation subsets: 43) Thus,
P(x) \(1123)
(15)
Final BIP objective:
OBIP = f((x) + {(11Ts)
(16)
E
The hypergraph max-cut problem (Sec. 6
The max-cut problem of hypergraph G (V, Æ) involves partitioning the vertex set into two disjoint subsets such that the number of hyperedges crossing the partitioned blocks is maximized.
PUBO Form. The hypergraph max-cut problem on G' can be formulated by optimizing a PUBO objective as follows:
min O mmax-ca cut
-
J.
II - x.)) iEe
(17)
<EE
where v; E {0, 1] are binary decision variables.
For simple example illustrated in Fig. 3 the original hypergraph consists of three hyperedges: {æ1, 12 {2z, }. and {x1, 22, /z}. Thus, the max-cut objective of G' is to minimize 2x1 + 2x - 2xg + 24 3 2143 22 2zzZ1. BIPNN typically generates new hypergraph structure with five hyperedges, {.1, ). {.z, }. 23), and {I2, F3), to solve this PUBO objective. we found that both hypergraphs can be utilized for HyperGNN training BIPNN framework.
F
Datasets and additional results
F1
Datasets
Table 4: Summary statistics six real-world graphs: the number of vertices [V], the number of edges LT]. Four hypergraphs: the number of vertices V/, the number of hyperedges E the size of the hypergraph Eeeg le).
Graphs
[V
E
Hypergraphs V
E
EeEg le|
BAT
131
1,003
Primary
242
12,704
30,729
EAT
399
5,993
High
327
7,818
18,192
UAT
1,190
13,599
Cora
1,330
1,503
4,599
DBLP
2,591
3.528
PubMed
3,824
7,523
33,687
CiteSeer
3,279
4,552
AmzPhoto 7,535
119,081
F.2 Comparison with Gurobi and SCIP
On larger-scale BIPs, the advantage of BIPNN becomes more pronounced. For SCIP and Gurobi, it often difficult to find an initial solution within reasonable time on large-scale BIPs. To illustrate this issue, we have supplemented the following experimental results.
15

---

Table 5: Comparison of BIPNN and BIP solvers such Gurobi and SCIP large-scale datasets.
Number of variables (monomials)
SCIP
Gurobi
BIPNN
10,000 (20,000)
-2,066
-1,870
-2,566
10,000 (30,000)
-005
-1,988
-3,317
10,000 (50,000)
-117
None
-4,23
20,000 (40,000)
None
None
-5,039
Tab. 5 shows optimization results of different methods on the objective function, with computation time constrained to half an hour. The degree of each monomial BIPNN outperforms SCIP and Gurobi.
F33
Comparison with Tabu Search
1.95
Ratio of Solutions
1.50
TABU
Ratio DF Splutions
1,80
TABU
BIPNN
1.65
BIPNN
1.35
1.50
1.20
1.05
1,29
1.05
0.90
0.75
0.75
1000
2000 1000 Number of Vertices
2000
5000
1000
3000 4000 5000 Number of Vertices
2000
(a) 4.
(b) d = 6.
Figure 8: Comparison of BIPNN and Tabu search. is the degree of polynomial terms in BIP objective functions. (a)(b) illustrate the ratio of the solutions of BIPNN to Tabu; Runtime is restricted half an hour.
Tabu search is heuristic method that typically provides approximate solutions. We impose half an hour time limit and evaluate the difference in solution quality for Tabu when the degrees of polynomial terms are set and 6. The number of vertices (variables) [V] in the hypergraph generated by BIPNN ranges from 200 to 5, 000. Experimental results are depicted in Fig. [a (d = 4) and Fig. 8b (d 6). As shown in the figures, BIPNN achieves the performance comparable to Tabu when the number of variables exceeds 1, 000. When the number of variables exceeds 2, 500, BIPNN significantly outperforms Tabu as the variable count increases further.
F,4
Comparison of various HyperGNNS
Table The performance of BIPNN with various HyperGNNs.
Datasets
HyperGNNs
Runtime (s)
VRAM (MB)
Number of
Cora
HGNN+
64
421
1,394
UniGCN
421
1,394
UniGAT
84
479
1,358
HyperGCN
4,517
533
1,317
Primary
HGNN+
S7
229
8,495
UniGCN
59
229
8,496
UniGAT
70
231
8,442
HyperGCN
4.818
235
8,363
High
HGNN+
46
177
5,227
UniGCN
179
5,213
UNiGAT
55
189
5,209
HyperGCN
3.367
233
5,118
We have evaluated the performance of BIPNN with various HyperGNNs, including HGNN+ UniGCN, UniGAT, and HyperGCN. HGNN+ always outperformed others in both training time
16

---

and VRAM usage. The evaluation results on the hypergraph max-cut problem have been depicted in Tab. The evaluation metries include runtime, VRAM consumption, and the number of cuts. We conduct the experiments on three hypergraph datasets, including Cora, Primary, and High, with all models trained for 5000 epochs.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In this paper, we introduce novel unsupervised neural network frameworks for solving nonlinear BIP problems. We provide theoretical justification and conduct extensive experiments on synthetic and real-world datasets.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We provided information on method limitations in section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
18

---

Answer: [Yes]
Justification: In section 3 and 2
where we discuss the proposed method's theoretical
proposition, we provide full set of assumptions and complete proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide a fully detailed experimental results in section 6 the code for experiments.
We also provided
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
19

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide the code of our experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //iiss.cc/pill wttp:ccppppcccceeeeeeeeee..c.ett httpa////giieee/eeeSSbiiiiisssss /Co///ooddiissssseeeeeee swi.isoicciyyyyciicc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
All implementation details for experiments have been provided in section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Section
We reported the standard deviation error of the mean and all the results in
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
20

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute resources used are presented in section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and ensured our compliance with its guidelines.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We believe this work does not have direct social impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
21

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: All the datasets used in this work are known and widely used. We aware of any risks involved in these datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We share all the packages we used for our code.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
22

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.paperssit
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
We document our experiments thoroughly, anonymize the data, and provide
the code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
23

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "u978rFRyR3", "reviewer": "Reviewer_d2xH", "summary": "This paper introduces BIPNN, an unsupervised learning framework for solving nonlinear Binary Integer Programming (BIP) problems. Its core idea is to reformulate a complex, nonlinear, and constrained BIP into an unconstrained polynomial binary optimization (PUBO) problem via polynomial and penalty methods. This PUBO problem is then modeled as a hypergraph and solved end-to-end by a Hypergraph Neural Network (HyperGNN). To enhance scalability, the authors also design a GPU-accelerated training algorithm and an annealing strategy.", "questions": "- How are nonlinear terms integrated into the hypergraph model and the GPU-accelerated PUBO loss function if they are not converted into polynomials?\n\n- What is the impact of precision errors from the polynomial approximation during continuous relaxation, especially for problems with tight equality constraints?\n\n- What are the key differences and advantages of BIPNN compared to recent, similar works like NeuralQP?\n\n- Why was an unsupervised approach chosen? What is the expected performance trade-off compared to a supervised method?\n\n- To validate the method's effectiveness, comparisons against a wider range of solvers (Gurobi, CPLEX) and on standard libraries (QPLIB) are essential. Are the authors willing to provide these crucial results? My assessment of the paper's significance would substantially increase with such additions.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper combines polynomial reformulation, hypergraph modeling, and unsupervised learning into a novel, end-to-end framework for the challenging class of nonlinear BIP problems.\n\n- The proposed GPU-acceleration algorithm effectively addresses the computational bottleneck of large-scale PUBO loss functions, which is a key step toward practical application.\n\n**Weaknesses:**\n\n- The paper's claim that complex nonlinear terms can be used directly in the loss function is not well-explained and seems to conflict with the hypergraph modeling, which is based on polynomial interactions.\n\n- The polynomial reformulation of functions like $\\text{sin}(x_1+x_2)$ can introduce precision errors when variables are relaxed to the continuous space, a critical issue for problems with tight constraints that the paper fails to address.\n\n- The paper does not adequately differentiate itself from recent and highly similar work using hypergraphs for optimization [1, 2], which weakens its originality claim.\n\n\n- The evaluation omits comparisons with major commercial solvers (e.g., Gurobi, CPLEX) and other specialized nonlinear solvers.\n\n- Crucially, the paper lacks experiments on established public benchmarks for nonlinear optimization, such as QPLIB[3], which significantly undermines its performance claims.\n\n- There is no discussion of the potential performance trade-offs of the chosen unsupervised approach versus supervised alternatives.\n\n[1] Distributed constrained combinatorial optimization leveraging hypergraph neural networks.\n\n[2] NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale QCQPs.\n\n[3] QPLIB: A library of quadratic programming instances.", "was_revised": true, "final_justification": "Given that the authors' comprehensive responses and, critically, the new empirical evidence have fully resolved my initial reservations, I have raised my score to positive. The paper is now in a much stronger position, and I believe it makes a valuable contribution to the field.", "rebuttal": "We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.\n> Question 1: How are nonlinear terms integrated into the hypergraph model and the GPU-accelerated PUBO loss function if they are not converted into polynomials?\n\nWe appreciate the reviewer’s concern. In this paper, we demonstrate that leveraging the binary nature of 0-1 variables allows the transformation of nonlinear terms (e.g., $\\rm{sin}$, $\\rm{log}$, $\\rm{exp}$) into polynomials. These can then be efficiently computed using the GPU-accelerated algorithm illustrated at the bottom of Figure 1. However, for specific problems, alternative approaches may yield superior solutions. Consider the example:\n\n$\\rm{sin}(x₁ + x₂) + \\rm{sin}(x₂ + x₃ + x₄) + \\rm{sin}(x₂ + x₄)$.\n\nHere, hyperedges {(1,2), (2,3,4), (2,4)} can be constructed in a hypergraph. When computing the loss function, two strategies emerge: (i) ​​Direct Calculation​​ without BIPNN's GPU acceleration; (ii) ​​Matrix Reformulation (BIPNN-inspired). Utilize the hypergraph's incidence matrix to first compute intermediate sums:$z₁ = x₁ + x₂$,$z₂ = x₂ + x₃ + x₄$,$z₃ = x₂ + x₄$, followed by element-wise application of $\\rm{sin}(·)$ to the vector $[z₁, z₂, z₃]$.\nThus, while BIPNN provides a general-purpose solution, specialized problem structures may benefit from tailored computational approaches.​\n\nBIPNN significantly accelerates polynomial-formulated nonlinear BIPs via GPU parallelization (Figure 1, bottom). However, as the reviewer noted, no efficient and universal acceleration method currently exists for BIPs with very complex nonlinear terms.\n\n> Question 2: What is the impact of precision errors from the polynomial approximation during continuous relaxation, especially for problems with tight equality constraints?\n\nWhen $\\rm{sin}(x₁ + x₂)<0.5$ appears in constraints​​, we can reformulate it as: $\\rm{sin}(x₁ + x₂)<0.4999$. We can then use polynomial and unconstrained reformulation. The term will be represented as a hyperedge $(x₁,x₂)$ to train the HyperGNN model. This creates a safety margin to compensate for potential floating-point errors.\n\n> Question 3: What are the key differences and advantages of BIPNN compared to recent, similar works like NeuralQP?\n\nWe noted the reviewer's doubts regarding the novelty of our work. In response, we have summarized the methods noted by reviewers​ 1 and reviewer 4 and plan to include this summary in the Appendix.\n\n| Method | Supervised  | Unsupervised | Reinforcement | Linear | Quadratic | Polynomial | Hypergraph_Modeling| ​​Publication_Info​ |\n| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |\n| BIPNN   |     | &#10003;    |     |     |     | &#10003;    | &#10003; (objective & constrain)   |\n| DiffILO [1]    |     | &#10003;    |     | &#10003;    |     |     |     |  ICLR 24'   |\n| HypOp [2] |     | &#10003;    |     |     |     | &#10003;    | &#10003; (only constrain)   | Nat. Mach. Intell. 23' |\n| NeuralQP [3]| &#10003;     |    |     |     |  &#10003;    |    | &#10003; (only constrain)   | pre-print |\n| MCPG [4]|     |    | &#10003;     |     |     | &#10003;     |  | pre-print |\n| VCA [5]|     | &#10003;     |    |     |  &#10003;     |    |  | Mach. Learn.: Sci. Technol. 23' |\n  \n[1] Differentiable Integer Linear Programming\\\n[2] HypOp: Distributed constrained combinatorial optimization leveraging hypergraph neural networks\\\n[3] Neuralqp: A general hypergraph-based optimization framework for large-scale qcqps\\\n[4] A Monte Carlo Policy Gradient Method with Local Search for Binary Optimization\\\n[5] Supplementing recurrent neural networks with annealing to solve combinatorial optimization problems\n| Method | Linear | Quadratic | Nonlinear |\n| -------- | -------- | -------- | -------- |\n| SCIP |  &#10003;   | &#10003;    |   &#10003;  |\n| Gurobi|  &#10003;   | &#10003;(only convex)    |    |\n| BIPNN |    |     | &#10003;    |\n1. Gurobi & SCIP. Gurobi is designed to solve linear programming (LP) and quadratic programming (QP). While SCIP is outperformed by Gurobi in solving LP and QP problems, SCIP provides capabilities for handling general non-linear BIP problems.\n\n2. DiffILO [1]. DiffILO is an unsupervised method with performance that can exceed Gurobi. Its methodology is the most similar to that of BIPNN. However, DiffILO employs bipartite graphs and GNNs to model constraints, whereas BIPNN utilizes HyperGNN to represent nonlinear BIPs. DiffILO is designed for linear BIPs, while BIPNN primarily addresses general nonlinear BIPs. Thus, our comparative analysis focuses on SCIP.\n\n3. HypOp [2]. HypOp is an unsupervised methods. Compared with HypOp, ​​BIPNN first discovers the mapping correspondence between polynomials and hypergraphs structures​​. Compared to linear and quadratic problems, ​​the core challenge in solving nonlinear BIPs lies in exploiting GPU acceleration during training​​. BIPNN proposes a computational framework specifically for this purpose. ​​In contrast, HypOp utilizes distributed HyperGNN training​​, yet its hypergraph modeling solely targets constraints rather than objective functions, thus rendering HypOp ​​inapplicable to general BIP problems.\n\n4. NeuralQP [3]. It is supervised and designed for QP problems. Supervised learning methods​​ require precomputing vast amounts of labels[1]. Obtaining labels for nonlinear BIPs is challenging, since ​​SCIP has higher computational overhead when solving nonlinear BIPs. Although NeuralQP demonstrates strong performance, it is specifically designed for QP problems. In contrast, BIPNN is designed for solving more complex nonlinear BIP problems, making it inherently difficult to match the performance of specialized QP solvers​​ such as NeuralQP.\n\n​​5. MCPG [4] and VCA [5]. Reinforcement learning methods typically exhibit slow training convergence. MCPG [4] improves reinforcement learning algorithms and achieves strong performance on three problems: graph max-cut, MIMO, and MaxSAT. VCA also demonstrates its performance on TSP and graph max-cut problems. However, we observe that these studies exclusively evaluate on specific CO problems, making it difficult to assess whether their methods generalize to general BIPs.\n\nFor example, it seems that MCPG requires designing customized filters for specific problems, and we don't understand how to create filters for hypergraph max-cut or general BIP problems. BIPNN's novel GPU acceleration techniques; polynomial reformulation; and unconstrained optimization mechanisms may potentially enhance other methods. \n\nOverall, BIPNN is proposed for general nonlinear BIPs, and it is fast. We believe ​​BIPNN and DiffILO collectively address numerous limitations inherent in penalty-based deep learning methods​​ for solving nonlinear BIP and ILP problems. In the future, they could potentially ​​integrate commercial solvers (e.g., Gurobi, SCIP) to enhance large-scale BIP optimization.\n\n> Question 4: Why was an unsupervised approach chosen? What is the expected performance trade-off compared to a supervised method?\n\n1. Most existing supervised methods are designed for ILP and QP problems. They require precomputing labels via solvers like Gurobi and SCIP. However, Gurobi can only solve linear and quadratic-cost BIP problems. SCIP and similar solvers exhibit ​​exponentially slower performance​​ when solving nonlinear BIPs compared to ILPs, making label acquisition practically infeasible.\nTo verify this, we measured SCIP’s runtime (s) for BIPs with polynomial objectives of degree 4.\n\n|Number of monomials|2400| 3600 | 4800 |6000|\n|--------|--------|--------|--------|--------|\n| Linear | 0.0037  | 0.0047  |0.0060 |0.0073 |\n| Nonlinear | 173  | 350  |  553  | 1215  |\n\n2. Recent work DiffILO [1] for linear BIPs reveals that supervised methods frequently produce infeasible solutions, due to the ​​misalignment between training objectives​​ (minimizing prediction error) ​​and inference objectives​​ (generating high-quality feasible solutions).\n\n> Question 5: To validate the method's effectiveness, comparisons against a wider range of solvers (Gurobi, CPLEX) and on standard libraries (QPLIB) are essential. Are the authors willing to provide these crucial results? My assessment of the paper's significance would substantially increase with such additions.\n\n**Gurobi does not support solving general nonlinear BIPs**. It cannot handle higher-degree polynomials (e.g., $x₁x₂x₃$), and non-convex QP problems.\n\nGurobi is designed to solve linear programming (LP) and quadratic programming (QP). While SCIP is outperformed by Gurobi in solving LP and QP problems, SCIP provides capabilities for handling general non-linear BIP problems. We tested Gurobi's performance on QPLIB and found that Gurobi solves QP problems with extremely high efficiency.\n\nWe recognize the reviewer’s concern on standard libraries such as QPLIB. However, BIPNN is designed for general nonlinear BIPs. Its optimization efficiency is suboptimal for LP/QP problems. We hope that in the future, researchers will establish benchmark datasets for nonlinear BIPs.\n\nTo compare Gurobi and BIPNN, we reformulated the hypergraph max-cut problem into linear BIPs and updated Tab. 1.\n\n| Method | BAT| EAT| UAT| DBLP| CiteSeer| Primary| High | Cora |\n| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |\n|GUROBI | **655** |**3997**| 8431|  **2869**|  **3960**| 8448| 5195| **1400**|\n|SCIP|  **655**  |3849 | 7899  | **2869**  |  **3960**   | 7603  | 4599  | 1215  |\n|Tabu|  652|3970|   8402|  2710| 3717| 8500| 5160| 1360|\n|BIPNN|   653|**3997**|  **8463**|  2847|  3944| **8516**| **5252**| 1397|\n\nWe find that GUROBI outperformed SCIP on all datasets, but BIPNN still achieved the best solutions on 4 datasets with larger objective function scales.\n\nWe are happy to provide additional clarifications and engage further in the discussions if we have misunderstood any crucial points.\n\nMany thanks, The Authors."}, {"review_id": "cAlYnBj1Bg", "reviewer": "Reviewer_yq35", "summary": "The authors propose a Hypergraph Neural Network (HyperNN) based solver for non-linear binary integer programming (BIP) problems. The proposed BIPNN approach reformulates BIP problems into unconstrained, differentiable and polynomial loss functions (PUBO formalism) that enable the training of a HyperGNN to solve these problems. This allows the method to be parallelizable on modern GPU hardware, making it significantly faster and more scalable than existing approaches. The authors provide clear explanations of how the BIP problems are reformulated into a unconstrained polynomial problem that can be used to train the HyperGNNs. An annealing strategy is used to ensure that the final solutions are binary. They show empirically that their method outperforms SOTA solvers on hypergraph max-cut problems and is comparable, sometimes outperforming) SOTA solvers on graph max-cut problems. They also show how the GPU parallelization enables their method to be significantly faster than SOTA solvers.", "questions": "### Questions\n- The authors use the term \"matrix\" to refer to the PUBO matrix Q but this seems to be simply the vector of coefficients, naming it \"matrix\" introduces a bit of confusion so maybe \"vector\" would be a better term for clarity.\n- How exactly does BIPNN generate a new hypergraph structure as opposed to the original hypergraph (Fig 3 & Sections 5 & 6)? This seems to be a central point in the experiments section but the phenomenon isn't clearly described. A brief discussion of how the generated hypergraph differs from the original one (perhaps with an example) would be beneficial.\n- What exactly is the ratio of solutions? (Fig 4 & Section 6) Are the solutions here on the max-cut problem therefore the \"solution\" is the number of cuts and higher is better or is it the cost-function of the PUBO problem? This is unclear from the text.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The paper is generally very well written, most important concepts are clearly explained.\n- The figures are well made and highly useful to clarify any concepts that might not be understood directly from the text itself.\n- The proposed method is innovative.\n- The empirical results properly showcase the benefits of the proposed methods.\n\n### Weaknesses\nWhile the paper is generally well written, some concepts could be better clarified:\n- The precise \"one-to-one\" mapping between polynomial BIP objectives and hypergraph structures is mentioned multiple times throughout the text and in the abstract and while this mapping is somewhat intuitive from figure 1 it is not described precisely in the text. When the authors mention this in the abstract it gives the impression that there will be some mathematical results/ that shows the existence of this mapping. More details about this would be beneficial.\n- A brief description of the inner workings of HyperGNNs would be useful to clarify these models for less familiar readers.\n- While the training workflow is clear from the text and highly useful Fig 1, I feel like the paper would benefit from a brief intuitive explanation of how Eq. 4 works with the training.\n- See the questions section for some others", "was_revised": true, "final_justification": "The authors have addressed my concerns and answered my questions. I maintain my score of 5 because I think this is a good paper but I'm not convinced the paper is sufficiently impactful to warrant a 6.", "rebuttal": "We thank the reviewer for their careful reading and comments. We address the weaknesses they mentioned below.\n> Weakness 1: The precise \"one-to-one\" mapping between polynomial BIP objectives and hypergraph structures is mentioned multiple times throughout the text and in the abstract and while this mapping is somewhat intuitive from figure 1 it is not described precisely in the text. When the authors mention this in the abstract it gives the impression that there will be some mathematical results/ that shows the existence of this mapping. More details about this would be beneficial.\n\nWe appreciate the reviewer’s feedback. Indeed the observation of mapping correspondence between polynomials and hypergraphs structures is crucial for understanding BIPNN. We will augment the caption of Fig. 1 with the following description:\n\nAs shown in c and d, BIPNN's hypergraph modeling (Sec. 3.1) stems from the key observation that when variables are treated as nodes, any monomial with coefficient $1$ can be represented as a hyperedge, while polynomials can be expressed through hypergraphs – and vice versa.\n\n> Weakness 2: A brief description of the inner workings of HyperGNNs would be useful to clarify these models for less familiar readers.\n\nWe appreciate the reviewer's valuable feedback. The following descriptions will be incorporated into Sec. 3.2:\n\nHyperGNNs​ are graph-based deep learning architectures that generalize GNNs to operate on hypergraphs. These HyperGNN models includes HGNN, HGNN+, HyperGCN, UniGCN (or UniGAT, UniSAGE, UniGIN). We have tested these models and observed that HGNN+ always outperformed other methods. Thus in this work we use HGNN+ to build BIPNN. The $l$-th convolutional layer of HGNN is built as below:\n\n$X^{(l)}={\\rm ReLU}{(D_v^{-\\frac{1}{2}}HWD_e^{-1}H^TD_v^{-\\frac{1}{2}}X^{(l-1)}\\Theta ^{(l)})}$\n\nwhere $X^{(l)}$ is the embedding matrix generated by the $l$-th convolutional layer.\nFor a vertex $v_i$ in the hypergraph, the degree is defined as $\\mathrm{deg}(v_i)=\\sum_{e_j\\in E}{H_{ij}}$.\nSimilarly, the degree of an edge $e_j\\in E$ is defined as $\\mathrm{deg}(e_j)=\\sum_{v_i\\in V}{H_{ij}}$.\n$D_v$ and $D_e$ are used to denote the diagonal matrices of the vertex degrees and edge degrees, respectively.\n$W=\\mathrm{diag}(|e_1|,...,|e_{|E|}|)$ can be regrarded as the weight of hyperedges.\nThe parameter $\\Theta^{(l)} \\in \\mathbb{R}^{d^{(l-1)}\\times d^{(l)}}$ is learned during training.\n\n> Weakness 3: While the training workflow is clear from the text and highly useful Fig 1, I feel like the paper would benefit from a brief intuitive explanation of how Eq. 4 works with the training.\n\nWe will provide the following explanation for Eq. 4:\n\nEq. 4 transforms the computation of large-scale polynomials into efficient matrix operations. It leverages PyTorch-supported broadcasting mechanisms to distribute the vector of decision variables across each monomial (hyperedge), enabling parallel computation.\n\n> Question 1: The authors use the term \"matrix\" to refer to the PUBO matrix Q but this seems to be simply the vector of coefficients, naming it \"matrix\" introduces a bit of confusion so maybe \"vector\" would be a better term for clarity.\n\nWe appreciate the reviewer's valuable feedback. We will fix this problem.\n\n> Question 2: How exactly does BIPNN generate a new hypergraph structure as opposed to the original hypergraph (Fig 3 & Sections 5 & 6)? This seems to be a central point in the experiments section but the phenomenon isn't clearly described. A brief discussion of how the generated hypergraph differs from the original one (perhaps with an example) would be beneficial.\n\nWe appreciate the reviewer's valuable feedback. The following descriptions will be incorporated into Sec. 6.3:\n\nUnlike conventional machine learning tasks (e.g., node classification), we hypothesize that the hypergraph structure for BIPNN should be related to the loss function. Thus HGNN's energy flow directs each polynomial term along proper gradient paths.\n\n\n\n> Question 3: What exactly is the ratio of solutions? (Fig 4 & Section 6) Are the solutions here on the max-cut problem therefore the \"solution\" is the number of cuts and higher is better or is it the cost-function of the PUBO problem? This is unclear from the text.\n\nWe appreciate the reviewer's valuable feedback. The following modification will be applied to line 251: $O_{\\rm BIPNN}^{s}$ and $O_{\\rm SCIP}^{s}$ are solutions (the number of cuts) obtained by BIPNN and SCIP.\n\nWe thank the reviewers for their feedback. We believe we have addressed the reviewer’s main concerns of this paper. We are happy to provide additional clarifications and engage further in the discussions if we have misunderstood any crucial points.\n\nMany thanks, The Authors."}, {"review_id": "z04lTqV1R5", "reviewer": "Reviewer_FymU", "summary": "This paper tries to solve a type of challenging optimization problem of nonlinear binary integer programming (BIP). This problem is fundamental in areas ranging from operations researches to chemical process control. It is hard problem due to its NP-completeness and the exploration of auxiliary variables in standard linearization schemes. \n\nBy deriving a one-to-one mapping between polynomial BIP objectives and hyper graph structures, the authors propose a new method called BIPNN. It is an unsupervised hyper graph neural-network (HyperGNN) that can be used to tackle BIP. The experimental results demonstrate its effectiveness. \n\nThe main contribution of this paper include\n1) A systematic way to reformulate constrained, discrete, nonlinear IBs into unconstrained polynomial (PUBO) loss functions and encode nonlinearities (isn, log, etc.) via low-degree polynomials.\n2) A continuous-annealing-enhanced training pipeline that performs gradient-based optimization end-to-end on the HyperGNN, avoiding costly branch-and-cut and auxiliary‐variable blowup. Also using GPU to speed up training. \n3) Good emperimental results on both synthetic hypergraphs (up to thousands of variables) and real-world graph/hypergraph max-cut benchmarks that BIPNN matches or outperforms other approaches in solution quality, while scaling well in time for fixed GPU resources .", "questions": "On Page 1, \"However, BIP is known to be NP-complete\". This is not accurate. Assignment problems and shortest path are BIP, but has polynomial algorithm. This sentence can change to \"However, BIP is generally known to be NP-complete\"?\n\nOn page 5, Section 4.2, \"where λ_k, μ_l are sufficiently large penalty coefficients\".  What is the guidance on choosing the “sufficiently large” λ_k and μ_l to avoid infeasibility or poor convergence?", "limitations": "Yes.", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The main strengths include\n1) Novel PUBO reformulation. The precise polynomial fitting of nonlinear terms for binary inputs enables an exact loss construction rather than heuristic linear relaxations .\n2) End-to-End differentiable HyperGNN solver. Modeling multi-variable interactions as hyperedges and training HyperGNN directly on the PUBO loss bypasses expensive combinatorial search, achieving scalability and leveraging GPU parallelism.\n3) Good empirical evaluation. Extensive benchmarks on both synthetic and real datasets, with comparisons against exact (SCIP) and heuristic (Tabu) solvers under a 1 hour limit, demonstrate BIPNN’s competitive performance, especially on larger instances.\n\nThe main weakness include \n1) Limited scalability of polynomial reformulation. The general transformation for multivariate nonlinearities causes exponential preprocessing in the number of variables per term, limiting applicability to only low-order interactions.\n2) No clear reasons of HyperGNN architectural choices. While several HyperGNN variants are cited, the paper lacks ablation on how different architectures (HGNN+, HyperGCN, UniGCN) affect performance or how hyperparameters were selected. The author should provide hyperparameter guidelines. Provide systematic methods or default settings (and sensitivity analysis) for choose proper values of λ, μ, γ, etc. to aid reproducibility.\n3) Weak Baselines. Comparison is confined to SCIP and Tabu, which are good open source code, but they are generally much worse than the MINLP solvers by Gurobi, FICO, etc. The baseline comparison should be strengthened by comparing with those solvers, so that the effectiveness and scalability of the proposed approach can be better justified.", "was_revised": true, "final_justification": "Thank you to the authors for the rebuttal. I remain unconvinced that this approach can be applied competitively to practical, large‑scale problems, so I am maintaining my score.", "rebuttal": "We thank the reviewer for their careful reading and comments. We treasure the opportunity to address your concerns and improve our work.\n> Weakness 1: Limited scalability of polynomial reformulation.\n\nThe polynomial reformulation approach proposed by BIPNN demonstrates how to handle simple nonlinear terms such as $\\rm{sin}$ and $\\rm{log}$. We think that leveraging GPU acceleration to train BIPNN for more generalized forms of nonlinear BIPs remains an open question worthy of further exploration.\n\nAs shown in Fig. 1 at the bottom, BIPNN provides a fast algorithm for polynomial-form BIPs. Consider the example:\\\n$\\rm{sin}(x₁+x₂) + \\rm{sin}(x₂+x₃+x₄) + \\rm{sin}(x₂+x₄)+\\rm{log}(x₁+x₂) + \\rm{log}(x₂+x₃+x₄) + \\rm{log}(x₂+x₄)$.\\\nTo train the HyperGNN model, hyperedges {(1,2), (2,3,4), (2,4)} can be constructed in a hypergraph. When computing the loss function, we can use: (i) ​​Direct Calculation​​ without BIPNN's GPU acceleration; (ii) ​​Matrix Reformulation (BIPNN-inspired). Utilize the hypergraph's incidence matrix to first compute intermediate sums:$z₁ = x₁+x₂$,$z₂ = x₂+x₃+x₄$,$z₃ = x₂+x₄$, followed by element-wise application of $\\rm{sin}(·)$ and $\\rm{log}(·)$ to the vector $[z₁, z₂, z₃]$.\n\nMoreover, we would like to emphasize that BIPNN's polynomial reformulation method can enhance all existing penalty-based BIP solvers. BIPNN's core innovation is that it introduces a method to map constraints (e.g., $x₁+3x₂-2<0$) to continuously differentiable polynomial penalties (QUBO or PUBO formalism), such as $x₂+x₁x₂$ or more simplified form $x₂$. The advantages lie in two aspects:\n1. Quantum annealers (e.g., D-Wave systems) can efficiently solve QUBO and PUBO problems. Our method thus extends quantum computing's applicability (line 197, page 6).\n2. BIPNN provides fast algorithms to compute polynomial losses (Fig.1 at the bottom).\n\n> Weakness 2: No clear reasons of HyperGNN architectural choices. The author should provide hyperparameter guidelines.\n\n1. We have tested HyperGNN models including HGNN+, HyperGCN, and UniGCN, and observed that HGNN+ always outperformed others in both training time and VRAM usage. Investigating HyperGNN's internal mechanisms seems to be irrelevant to this work, ​​therefore​​ we omitted ablation studies. We appreciate the reviewer's suggestion and will incorporate comparative experiments in the appendix.\\\nWe evaluate the VRAM consumption and runtime performance of various HyperGNNs on the Cora dataset, with all models trained for 2000 epochs. The results are presented in the table.\n| Method | HGNN+| HyperGCN| UniGCN| UniGAT|\n| -------- | -------- | -------- | -------- | -------- |\n| VRAM usage (mb)| **964**    | 966   |  968   |  970   |\n| Runtime (s)| **25.3** | 1780 |  26 |  33.6 |\n\n2. We appreciate the reviewer's valuable feedback. In common Maximal Independent Set (MIS) problems, the penalty coefficient is typically fixed at 2. However, for ​​general BIP problems​​, the choice of penalty coefficient critically impacts both ​​constraint satisfaction​​ and ​​solution quality​​. This problem has been well-solved by DiffILO [1] (an unsupervised linear BIP solver) in 2024. Specifically, we can use\\\n$\\mu_l=\\mu_0+\\eta \\cdot q_l$\\\nwhere $\\mu_0$ is the initial value of the penalty coefficient $\\mu_l$, $\\eta$ is the learning rate, and $q_l$ is the value of the penalty term, which represents its deviation from $0$.\nWe initialize $\\mu_0$ with a ​​small value​​ (e.g., $2\\sim 5$) to broaden the model's search space. The learning rate​​ $\\eta$ should be experimentally tuned across different values (e.g., $0.001\\sim 1$）. Full hyperparameter guidelines will be comprehensively documented in the appendix.\\\n[1] Differentiable integer linear programming\n\n> Weakness 3: Weak Baselines.\n\nWe appreciate the reviewer's valuable feedback. Gurobi is known for its speed and efficiency in solving optimization problems. However, **Gurobi is designed for linear programming (LP), mixed-integer programming (MIP), and quadratic programming (QP)**. While SCIP is outperformed by Gurobi in solving LP and QP problems, SCIP provides capabilities for handling general non-linear BIP problems.\n​​ \n| Method | Linear | Quadratic | Nonlinear |\n| -------- | -------- | -------- | -------- |\n| SCIP |  &#10003;   | &#10003;    |   &#10003;  |\n| Gurobi|  &#10003;   | &#10003;(only convex)    |    |\n| BIPNN |    |     | &#10003;    |\n\nWe reformulated the hypergraph max-cut problem into linear BIPs and updated Tab. 1.\n​​\n| Method | BAT| EAT| UAT| DBLP| CiteSeer| Primary| High | ​Cora​ |\n| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |\n|GUROBI |   **655**  |**3997**|   8431|  **2869**|  **3960**| 8448| 5195| **1400**|\n|SCIP|   **655**  |3849    |   7899  |  **2869**   |  **3960**   | 7603  | 4599  | 1215  |\n|Tabu|   652|3970|   8402|  2710|  3717| 8500| 5160| 1360|\n|BIPNN|   653|**3997**|  **8463**|  2847|  3944| **8516**| **5252**| 1397|\n\nWe find that GUROBI outperformed SCIP on all datasets, but BIPNN still achieved the best solutions on 4 datasets with larger objective function scales.\n\n> Question 1: On Page 1, \"However, BIP is known to be NP-complete\". This is not accurate. Assignment problems and shortest path are BIP, but has polynomial algorithm. This sentence can change to \"However, BIP is generally known to be NP-complete\"?\n\nWe appreciate the reviewer's valuable suggestion. We will fix this problem.\n\n> Question 2: On page 5, Section 4.2, \"where λ_k, μ_l are sufficiently large penalty coefficients\". What is the guidance on choosing the “sufficiently large” λ_k and μ_l to avoid infeasibility or poor convergence?\n\nWe answer this question in Weakness 2.\n\nOverall, we thank the reviewers for their feedback. We believe we have addressed the reviewer’s main concerns about the experimental results of this paper. We are happy to provide additional clarifications and engage further in the discussions if we have misunderstood any crucial points.\n\nMany thanks, The Authors."}, {"review_id": "WsSeejdfRE", "reviewer": "Reviewer_QdA1", "summary": "To handle nonlinearities, most current solvers employ linear relaxations, authors proposed BIPNN (Binary Integer Programming Neural Network), an unsupervised learning framework to solve nonlinear BIP problems via hypergraph neural networks (HyperGNN). The authors also show the performance on synthetic and real-world datasets highlight the superiority of approach on maxcut problem. They compare the approach with SCIP and tabu search.\n\nHowever, there are several weaknesses, and the quality should be improved.", "questions": "no", "limitations": "1, In abstract, authors said “Yet, they lack scalability for tackling nonlinear challenges”, however, I did not see the  scalability of your proposed approach. Plz show this metric. \n\n2, what’s PUBO?\n\n3, in abstract, “reformulates BIPs-constrained, discrete, and nonlinear (sin, log, exp) optimization problems-into unconstrained, differentiable, and polynomial loss functions”, the eqn 7 may be not differentiable.\n\n4, the performance evaluation, plz compare the SOTA solver such as GUROBI, some problem-specific algorithms, and several RL methods such as [1][2]. \n\n5, The novelty of the proposed approach is not very clear. Some works such as [1] [2] have proposed to transfer BIP to unconstrained problems. \n\n[1] A Monte Carlo Policy Gradient Method with Local Search for Binary Optimization, \n\n[2] Supplementing recurrent neural networks with annealing to solve combinatorial optimization problems", "rating": 2, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "strengths: authors propose an unsupervised learning framework, named as BIPNN (Binary Integer Programming Neural Network), to solve nonlinear BIP problems via hypergraph neural networks (HyperGNN). \n\nWeaknesses:\n\n the idea is not very novel since some researchers have proposed similar approaches. Many researchers propose QUBO or Ising model [1] to solve this kind of problems. The depth of the paper  should also be improved. I suggest authors to read more current works such as [1]\n\n[1] A Monte Carlo Policy Gradient Method with Local Search for Binary Optimization,", "was_revised": true, "final_justification": "Ok.", "rebuttal": "We thank the reviewer for their careful reading and comments. We treasure the opportunity to address your concerns and improve our work.\n\n> Limitation 1: In abstract, authors said “Yet, they lack scalability for tackling nonlinear challenges”, however, I did not see the contribution on scalability.\n\nThe scalability of BIPNN lies in two aspects:\n1. It is computationally efficient. In Fig. 6, we demonstrate that without using BIPNN's fast algorithm   (Fig. 1 at the bottom), the computation time for the polynomial objective function during forward propagation grows rapidly as the problem size increases.\n2. Polynomial reformulation of various nonlinear terms. It employs polynomial reformulation to transform simple nonlinear terms (e.g., $\\rm{sin}$, $\\rm{log}$) into polynomials (Sec. 4). This is crucial because BIPNN provides a fast computational framework for polynomial objective functions.\n\n> Limitation 2: what’s PUBO?\n\nPUBO is Polynomial Unconstrained Binary Optimization, we clarified it in ​​Footnote 1 on Page 2​​.\n\n> Limitation 3: in abstract, “reformulates BIPs-constrained, discrete, and nonlinear (sin, log, exp) optimization problems-into unconstrained, differentiable, and polynomial loss functions”, the eqn 7 may be not differentiable.\n\nOn line 172, we explicitly state the non-differentiability of Eq. 7. This is why we use ReLU-based penalty method (line 174).\nHowever, if polynomial reformulation is adopted (see Appendix B), the polynomial penalty terms (line 176) will be differentiable.\n\nTo ensure the accuracy of the description, we will revise it as \"​​differentiable (almost everywhere)\".\n\n> Limitation 4: the performance evaluation, plz compare the SOTA solver such as GUROBI, and several RL methods such as [1] .\n\nWe appreciate the reviewer's valuable feedback. **Gurobi does not support solving general nonlinear BIP problems. Gurobi is designed to solve linear programming (LP) and quadratic programming (QP)**. It cannot handle cubic or higher-degree polynomials (e.g., $x₁x₂x₃$), and non-convex QP problems. While SCIP is outperformed by Gurobi in solving LP and QP problems, SCIP provides capabilities for handling general non-linear BIP problems. We tested Gurobi's performance on QPLIB and found that Gurobi solves QP problems with extremely high efficiency.\n\n| Method | Linear | Quadratic | Nonlinear |\n| -------- | -------- | -------- | -------- |\n| SCIP |  &#10003;   | &#10003;    |   &#10003;  |\n| Gurobi|  &#10003;   | &#10003;(only convex)    |    |\n| BIPNN |    |     | &#10003;    |\n\nTo address the reviewer's concern, we reformulated the hypergraph max-cut problem into linear BIPs and updated Tab. 1.\n\n| Method | BAT| EAT| UAT| DBLP| CiteSeer| Primary| High | ​Cora​ |\n| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |\n|GUROBI |   **655**  |**3997**|   8431|  **2869**|  **3960**| 8448| 5195| **1400**|\n|SCIP|   **655**  |3849    |   7899  |  **2869**   |  **3960**   | 7603  | 4599  | 1215  |\n|Tabu|   652|3970|   8402|  2710|  3717| 8500| 5160| 1360|\n|BIPNN|   653|**3997**|  **8463**|  2847|  3944| **8516**| **5252**| 1397|\n\nWe find that GUROBI outperformed SCIP on all datasets, but BIPNN still achieved the best solutions on 4 datasets with larger objective function scales.\n\n> Limitation 5: The novelty of the proposed approach is not very clear. [1] [2] proposed to transfer BIP to unconstrained problem.\n\nThe reviewer ​​observes​​ that penalty methods have been previously applied [1], [2]. Penalty methods are well-known techniques in CO. BIPNN's core innovation is that it introduces a method to map constraints (e.g., $x₁+3x₂-2<0$) to continuously differentiable polynomial penalties (QUBO or PUBO formalism), such as $x₂+x₁x₂$ or more simplified form $x₂$. The advantages lie in two aspects:\n1. Quantum annealers (e.g., D-Wave systems) can efficiently solve QUBO and PUBO problems. Our method thus extends quantum computing's applicability.\n2. BIPNN provides fast algorithms to compute polynomial losses (Fig.1 at the bottom).\n\nWe noted the reviewer's doubts regarding the novelty of our work. In response, we have summarized the methods noted by reviewers​ 1 and reviewer 4 and plan to include this summary in the Appendix.\n\n| Method | Supervised  | Unsupervised | Reinforcement | Linear | Quadratic | Polynomial | Hypergraph_Modeling| ​​Publication_Info​ |\n| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |\n| BIPNN   |     | &#10003;    |     |     |     | &#10003;    | &#10003; (objective & constrain)   |\n| DiffILO [1]    |     | &#10003;    |     | &#10003;    |     |     |     |  ICLR 24'   |\n| HypOp [2] |     | &#10003;    |     |     |     | &#10003;    | &#10003; (only constrain)   | Nat. Mach. Intell. 23' |\n| NeuralQP [3]| &#10003;     |    |     |     |  &#10003;    |    | &#10003; (only constrain)   | pre-print |\n| MCPG [4]|     |    | &#10003;     |     |     | &#10003;     |  | pre-print |\n| VCA [5]|     | &#10003;     |    |     |  &#10003;     |    |  | Mach. Learn.: Sci. Technol. 23' |\n  \n[1] Differentiable Integer Linear Programming\\\n[2] HypOp: Distributed constrained combinatorial optimization leveraging hypergraph neural networks\\\n[3] NeuralQP: A general hypergraph-based optimization framework for large-scale qcqps\\\n[4] A Monte Carlo Policy Gradient Method with Local Search for Binary Optimization\\\n[5] Supplementing recurrent neural networks with annealing to solve combinatorial optimization problems\n\n1. DiffILO [1]. DiffILO is an unsupervised method with performance that can exceed Gurobi. Its methodology is the most similar to that of BIPNN. However, DiffILO employs bipartite graphs and GNNs to model constraints, whereas BIPNN utilizes HyperGNN to represent nonlinear BIPs. DiffILO is designed for linear BIPs, while BIPNN primarily addresses general nonlinear BIPs. Thus, our comparative analysis focuses on SCIP.\n\n2. HypOp [2]. HypOp is an unsupervised methods. Compared with HypOp, ​​BIPNN first discovers the mapping correspondence between polynomials and hypergraphs structures​​. Compared to linear and quadratic problems, ​​the core challenge in solving nonlinear BIPs lies in exploiting GPU acceleration during training​​. BIPNN proposes a computational framework specifically for this purpose. ​​In contrast, HypOp utilizes distributed HyperGNN training​​, yet its hypergraph modeling solely targets constraints rather than objective functions, thus rendering HypOp ​​inapplicable to general BIP problems.\n\n3. NeuralQP [3]. It is supervised and designed for QP problems. Supervised learning methods​​ require precomputing vast amounts of labels[1]. Obtaining labels for nonlinear BIPs is challenging, since ​​SCIP has higher computational overhead when solving nonlinear BIPs. Although NeuralQP demonstrates strong performance, it is specifically designed for QP problems. In contrast, BIPNN is designed for solving more complex nonlinear BIP problems, making it inherently difficult to match the performance of specialized QP solvers​​ such as NeuralQP.\n\n4. MCPG [4] and VCA [5]. Reinforcement learning methods typically exhibit slow training convergence. MCPG [4] improves reinforcement learning algorithms and achieves strong performance on three problems: graph max-cut, MIMO, and MaxSAT. VCA also demonstrates its performance on TSP and graph max-cut problems. However, we observe that these studies exclusively evaluate on specific CO problems, making it difficult to assess whether their methods generalize to general BIPs.\n\nFor example, it seems that MCPG requires designing customized filters for specific problems, and we don't understand how to create filters for hypergraph max-cut or general BIP problems. BIPNN's novel GPU acceleration techniques; polynomial reformulation; and unconstrained optimization mechanisms may potentially enhance other methods. \n\nIn summary, BIPNN is proposed for general nonlinear BIPs, and it is fast. We believe ​​BIPNN and DiffILO collectively address numerous limitations inherent in penalty-based deep learning methods​​ for solving nonlinear BIP and ILP problems. In the future, they could potentially ​​integrate commercial solvers (e.g., Gurobi, SCIP) to enhance large-scale BIP optimization.\n\nWe thank the reviewers for their feedback. We believe we have addressed the reviewer’s main concerns about the novelty of this paper. We are happy to provide additional clarifications and engage further in the discussions if we have misunderstood any crucial points.\n\nMany thanks, The Authors."}]

Author rebuttal:

Meta-review: This paper presents BIPNN (Binary Integer Programming Neural Network), an unsupervised learning framework to solve nonlinear BIP problems via hypergraph neural networks. This work converts constrained BIP problems with nonlinear ($\sin$, $\log$, $\exp$) terms into a polynomial unconstrained binary optimization (PUBO) formalism, and then uses a continuous-annealing-enhanced unsupervised training pipeline leveraging hypergraph neural networks to minimize the PUBO objective. It further proposes a GPU-acceleration algorithm to improve computational efficiency. An empirical study of the performance of BIPNN is provided on synthetic hypergraphs (up to thousands of variables) and real-world graph/hypergraph max-cut benchmarks.


Strengths:
* The paper combines polynomial reformulation, hypergraph modeling, and unsupervised learning into a novel, end-to-end framework for the challenging class of nonlinear BIP problems.
* The GPU-accelerated PUBO loss formulation addresses an important computational bottleneck.
* The algorithm is evaluated extensively.  BIPNN matches or outperforms other approaches (SCIP and Tabu) in solution quality, while scaling reasonably in terms of solution time under fixed GPU resources. During the rebuttal period, the authors additionally compared against Gurobi, showing comparable quality of results on small-/medium-scale problems, and ability to find solutions under a reasonable time budget in large-scale scenarios where Gurobi could not.


Weaknesses:
* The method is limited to simple nonlinear terms such as $\sin$ and $\log$. The general transformation for multivariate nonlinearities can incur exponential preprocessing in the number of variables per term; the paper does not address this more general setting.


Other major points of discussion:
* Reviewer FymU pointed out that the HyperGNN architectural choices were not well justified. The authors provided a comparison of different HyperGNN models in their response, and indicated they would include this in the appendix.
* Reviewer d2xH raised questions about the impact of prediction errors. The authors clarified that they include a (small) safety margin on constraints.
* Several reviewers indicated that the paper does not adequately differentiate itself from recent and similar work using hypergraphs for optimization. The authors provided a comparative table of methods and indicated why the prior literature is developed for different or more specialized settings.
* There was significant back-and-forth about initial lack of comparison to Gurobi, which the authors initially claimed was not applicable to BIPs, but later realized was. Upon this, the authors followed up with additional comparisons to Gurobi. Some reviewers felt this sufficiently improved the quality of experiments; other reviewers felt the comparisons were still insufficient, and more generally that the authors' lack of knowledge about Gurobi handling this problem setting had affected their confidence in the authors' knowledge of this area and therefore the paper's technical claims.


Overall, considering both the initial submission and rebuttal, the paper provides an interesting and convincing algorithm to an important class of problems, differentiates itself from prior literature, and provides informative experimental comparisons against strong baselines. I therefore recommend acceptance.
Decision: Accept (poster)