Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks

Minshuo Li; Yaoxin Wu; Pavel Troubil; Yingqian Zhang; Wim P. M. Nuijten

cs.NEMar 16, 2026

Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks

Authors: Minshuo Li, Yaoxin Wu, Pavel Troubil, Yingqian Zhang, Wim P. M. Nuijten

Organizations: Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, the Netherlands · Eindhoven Artificial Intelligence Systems Institute, Eindhoven University of Technology, Eindhoven, the Netherlands · Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, Eindhoven, the Netherlands · Delmia R&D, Dassault Systèmes, ’s-Hertogenbosch, the Netherlands

Abstract

Complex real-world optimization problems often involve both discrete decisions and nonlinear relationships between variables. Many such problems can be modeled as polynomial-objective integer programs, encompassing cases with quadratic and higher-degree variable interactions. Nonlinearity makes them more challenging than their linear counterparts. In this paper, we propose a hypergraph neural network (HNN) based method to solve polynomial-objective integer programming (POIP). Besides presenting a high-degree-term-aware hypergraph representation to capture both high-degree information and variable-constraint interdependencies, we also propose a hypergraph neural network, which integrates convolution between variables and high-degree terms alongside convolution between variables and constraints, to predict solution values. Finally, a search process initialized from the predicted solutions is performed to further refine the results. Comprehensive experiments across a range of benchmarks demonstrate that our method consistently outperforms both existing learning-based approaches and state-of-the-art solvers, delivering superior solution quality with favorable efficiency. Note that our experiments involve both polynomial objectives and constraints, demonstrating our HNN's versatility for general POIP problems and highlighting its advancement over the existing literature.

Figures & tables

Figure 1: The framework of the proposed method. For a POIP instance shown in a), our method first transforms it into a hypergraph shown in b), where orange dashed circles denote hyperedges representing high-degree terms. Their raw features (term coefficients and variable degrees) are illustrated in the orange dashed boxes. This hypergraph is then processed by a hypergraph neural network shown in c) for representation learning and solution prediction, where

h_{\epsilon}

h_{v}^{(i)}

, and

h_{c}^{(i)}

represent hyperedge embeddings, variable embeddings after the

i

-th update, and constraint embeddings after the

i

-th update, respectively. Finally, a neighborhood-search based repair-and-refinement process, shown in d), turns the predicted results into a high-quality feasible solution.

Method	Train	Base solver: Gurobi					Base solver: SCIP
Method	Train	1k	2k	5k	10k	Overall	1k	2k	5k	10k	Overall
Exact solver	–	$0.38$	$0.23$	$29.08$	$26.69$	14.10 ${}_{\pm 13.89}^{*}$	$5.15$	$6.10$	$35.73$	$27.61$	18.65 ${}_{\pm 13.38}^{*}$
Neural QP	Mini	$0.35$	$0.09$	$0.03$	$0.03$	0.11 ±0.13	0.54	0.11	29.38	17.90	12.99 ±13.21
	1k	$0.35$	$0.09$	$0.04$	$0.04$		0.38	0.11	28.68	19.44
	2k	–	$0.09$	$0.05$	$0.04$		–	0.10	29.54	17.41
GNNQP	Mini	$0.45$	$0.09$	$0.05$	$0.03$	7.22 ${}_{\pm 15.00}^{*}$	0.54	0.11	29.38	17.90	16.08 ±15.52

Table 1: Comparison on QMKP datasets in terms of mean and standard deviation of

\mathrm{gap_{\%}}

. The best results are highlighted in bold and ∗ indicates the overall results are statistically different from the best one. “–” denotes that the corresponding test was omitted, as models were only evaluated on instances with identical or larger scales than the training instances, following the setting in [ 47 ] .

Method	Train	Base solver: Gurobi				Base solver: SCIP
Method	Train	150 $\times$ 30	200 $\times$ 30	500 $\times$ 100	Overall	150 $\times$ 30	200 $\times$ 30	500 $\times$ 100	Overall
Exact Solver	–	51.42	58.20	38.66	48.89 ${}_{\pm 11.11}^{*}$	66.17	73.11	72.31	69.14 ${}_{\pm 4.68}^{*}$
Neural QP	50 $\times$ 10& 50 $\times$ 20	28.03	42.92	23.82	37.04 ${}_{\pm 13.95}^{*}$	54.63	62.65	71.52	62.09 ${}_{\pm 8.09}^{*}$
Neural QP	150 $\times$ 30& 200 $\times$ 30	42.20	62.18	26.47	37.04 ${}_{\pm 13.95}^{*}$	58.08	67.11	69.90	62.09 ${}_{\pm 8.09}^{*}$
Ours	50 $\times$ 10& 50 $\times$ 20	9.95	8.96	2.78	6.59 ±6.39	31.52	21.05	62.62	42.01 ±16.67
Ours	150 $\times$ 30& 200 $\times$ 30	5.23	7.08	2.65	6.59 ±6.39	29.97	46.31	62.36	42.01 ±16.67

Table 2: Comparison on CFLPTC datasets in terms of mean and standard deviation of

\mathrm{gap_{\%}}

. The best results are highlighted in bold and ∗ indicates the overall results are statistically different from the best one.

Instance ID	Gurobi	NeuralQP	GNNQP	TriGNN	Ours
2315	59.75	15.92	13.10	12.54	13.49
2733	1.38	0.28	0.18	0.10	0.38
2957	2.11	2.07	1.88	1.13	0.71
3347	0.52	0.20	9.28	5.93	0.34
3402	2.80	7.10	4.95	4.12	6.64
3584	66.75	15.04	7.75	15.59	15.03

Table 3: Comparison on QPLIB instances by mean value and standard deviation of

\mathrm{gap_{\%}}

. The best and second best results are highlighted in bold and italics, respectively. ∗ indicates statistically significant difference to the best result.

Method	Train	Base solver: Gurobi					Base solver: SCIP
Method	Train	1k	2k	5k	10k	Overall	1k	2k	5k	10k	Overall
Exact solver	–	3.21	6.45	5.83	9.88	6.34 ${}_{\pm 9.84}^{*}$	38.82	42.08	53.12	53.07	46.77 ${}_{\pm 6.60}^{*}$
Neural QP	Mini	0.47	0.43	0.25	0.22	0.33 ${}_{\pm 0.22}^{*}$	0.60	0.51	0.37	0.31	0.43 ${}_{\pm 0.23}^{*}$
	1000	0.54	0.42	0.22	0.22		0.62	0.50	0.36	0.32
	2000	–	0.39	0.25	0.19		–	0.47	0.34	0.29
GNNQP	Mini	3.53	2.29	3.23	3.36	3.07 ${}_{\pm 0.68}^{*}$	3.60	2.40	3.29	3.42	3.14 ${}_{\pm 0.66}^{*}$

Table 4: Results on RandQCP datasets by mean and standard deviation of

\mathrm{gap_{\%}}

. The best results are highlighted in bold and ∗ indicates the overall results have statistically significant difference to the best one.

	NeuralQP-HD	GNNQP-HD	w/o-VCConv	w/o-HyConv	Ours
1k	0.33	0.36	0.42	0.30	0.31
2k	0.90	2.16	1.92	0.81	0.10
Average	0.61	1.26	1.17	0.56	0.20

Table 5: Comparison of our model and ablation baselines on QMKP instances in terms of

\mathrm{gap_{\%}}

. The best result of each testing dataset is highlighted in bold.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Tensor	Feature	Description
$\mathcal{V}$	type	(continuous, binary, integer) as a one-hot encoding
	lb	Lower bound value of the variable
	up	Upper bound value of the variable
	inf_lb	Binary indicator (1 if the lower bound is negative infinity, 0 otherwise)
	inf_ub	Binary indicator (1 if the upper bound is positive infinity, 0 otherwise)
	avg_obj_coe	Average value of coefficients associated with this variable in the objective function

Appendix

Table 6: Raw Features of High-Degree Term-Aware Hypergraph Representation

Dataset	Number	$m$	$n$	Coordinate	$D_{j}$	$o_{i}$	$C_{i}$
1	1605	50	10	$U(10,200)$	$U(10,50)$	$U(300,700)$	$U(100,500)$
2	1119	50	20	$U(10,200)$	$U(30,80)$	$U(300,700)$	$U(100,500)$
3	984	150	30	$U(10,300)$	$U(10,50)$	$U(300,700)$	$U(200,600)$
4	200	200	30	$U(10,200)$	$U(10,50)$	$U(500,1500)$	$U(500,800)$

Appendix

Table 7: Setting for CFLPTC Training Dataset Generation

Method	NeuralQP	Ours
$\mathrm{gap}_{\%}$	99.10	71.92

Appendix

Table 8: Comparison on QMKP-1k datasets in terms of prediction performance.

Method	Train	Base solver: Gurobi
Method	Train	150 $\times$ 30	200 $\times$ 30	500 $\times$ 100	Overall
Exact Solver	–	51.42	58.20	38.66	48.89 ${}_{\pm 11.11}^{*}$
Neural QP	50 $\times$ 10& 50 $\times$ 20	28.03	42.92	23.82	37.04 ${}_{\pm 13.95}^{*}$
Neural QP	150 $\times$ 30& 200 $\times$ 30	42.20	62.18	26.47	37.04 ${}_{\pm 13.95}^{*}$
Ours –Quad	50 $\times$ 10& 50 $\times$ 20	32.49	38.40	11.25	29.77 ${}_{\pm 25.23}^{*}$
Ours –Quad	150 $\times$ 30& 200 $\times$ 30	31.45	39.77	11.46	29.77 ${}_{\pm 25.23}^{*}$

Appendix

Table 9: Comparison on CFLPTC datasets in terms of mean and standard deviation of

\mathrm{gap_{\%}}

. The best results are highlighted in bold and ∗ indicates the overall results are statistically different from the best one.

Methods	Base solver
Methods	Gurobi	SCIP
Exact solver	5.12	13.61
NeuralQP	0.10	4.95
GNNQP	1.18	5.94
TriGNN	0.12	5.03
Ours	0.08	4.75

Appendix

Table 10: Comparison on QMKP datasets in terms of SGM (shift=1) of

\mathrm{gap_{\%}}

. The best results are highlighted in bold.

Method	Train	1k	2k	5k	10k	Overall
Gurobi	–	$0.45$	$0.22$	$28.82$	$24.89$	$13.59$
Neural QP	Mini	$0.35$	$0.08$	$0.04$	$0.03$	0.11
	1k	$0.36$	$0.09$	0.03	$0.04$
	2k	–	$0.09$	$0.05$	$0.03$
Ours	Mini	0.17	0.10	$0.03$	0.04	0.09
	1k	$0.31$	$0.10$	$0.05$	$0.04$

Appendix

Table 11: Comparison of our method, NeuralQP and Gurobi under multiple solver random seeds on QMKP datasets in terms of mean

\mathrm{gap_{\%}}

. The best results are highlighted in bold.

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 381 papers

Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization
Aug 31, 2026Jessica D. Elrefaei, Kaixun Hua, Seungbae Kim +2Graph Neural Networks Value Function Estimation
A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention
Jan 8, 2026Peixin Huang, Yaoxin Wu, Yining Ma +3Graph Neural Networks Mixed-Integer Linear Programming
Shenzhen Research Institute, Shandong University, China
Autoregressive Differentiable Method for Integer Programming
Oct 1, 2026Ouns El Harzli, Yudong CaoCombinatorial Optimization Neural Combinatorial Optimization
BCG X AI Science Institute Boston, USA · Zapata Quantum Boston, USA

Aug 31, 2026J/K move · Enter open · S save

Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization

Jessica D. Elrefaei, Kaixun Hua, Seungbae Kim, Hoang Nam Tran+1

Graph Neural Networks Value Function Estimation Mixed-Integer Linear Programming Combinatorial Optimization Bilevel Optimization

Open paper AskPDF arXiv

Bilevel mixed-integer linear optimization problems model hierarchical decision processes in which a leader anticipates the optimal response of a follower. Although expressive, these problems are computationally challenging because lower-level optimality is embedded in the leader's feasible region. Value-function reformulations replace the nested follower optimization with a constraint involving the follower's optimal value, but evaluating this value function exactly can itself be expensive. This paper introduces Graph4BiLO, a graph neural network (GNN) approach for learning bilevel value functions from variable--constraint graph representations. In contrast to fixed-length multilayer perceptron (MLP) representations, the GNN uses shared message-passing parameters and can therefore be applied across multiple problem sizes with a single trained model. The learned ReLU network is encoded exactly as mixed-integer linear constraints and embedded in an approximate single-level formulation. A repair step subsequently re-solves the follower problem for the selected leader decision to recover a bilevel-feasible follower response. We evaluate Graph4BiLO on knapsack interdiction instances with 20--100 items against the exact MibS solver and the learning-based Neur2BiLO method. Graph4BiLO obtains objective values comparable to Neur2BiLO across all tested sizes while avoiding size-specific neural networks. An additional out-of-distribution experiment demonstrates zero-shot transfer from 20-item training instances to previously unseen 40- and 60-item instances. However, embedding message passing at every graph node substantially increases the resulting mixed-integer formulation size and solve time. These results identify a central tradeoff between size-generalizable graph representations and the computational cost of embedding GNNs within optimization models.

Abstract

Combinatorial Optimization

Explore similar work

Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization

A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention

Autoregressive Differentiable Method for Integer Programming