EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference

Niki Triantafyllou; Maria M. Papathanasiou

cs.LGOct 24, 2026

EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference

Authors: Niki Triantafyllou, Maria M. Papathanasiou

Organizations: Sargent Centre for Process Systems Engineering, Department of Chemical Engineering Imperial College London

Abstract

Learning-based approaches to combinatorial optimization often predict solutions directly or use predictions to restrict search, while expressive energy-based models typically rely on approximate inference. We introduce EnerGNN, a framework that learns energy functions over complete binary configurations and minimizes them under explicit hard constraints through mixed integer programming (MIP). EnerGNN combines a graph neural network encoder with an optimization-compatible readout and a nonlinear energy head, enabling exact constrained inference over the learned energy. An optimality-aware contrastive loss trains the energy to reflect solution quality and constraint violations. Across Quadratic Knapsack, Combinatorial Auctions, and a personalized cell therapy supply chain problem, EnerGNN achieves near-optimal solutions with 100% feasibility. On the supply chain problem, it achieves a 0.05% mean primal gap and a 17.4 $\times$ speedup over the monolithic MIP. The learned energy also generalizes to larger instances and supports zero-shot constraint injection, adapting to changing constraints without retraining while preserving feasibility.

Figures & tables

Figure 1: EnerGNN encodes an optimization instance using a bipartite message-passing GNN, learns an optimization-compatible energy function over binary configurations, and performs exact constrained inference by globally minimizing the learned energy over the encoded feasible set.

	QKP				CART				CA
Method	Gap (%)	Time (s)	$\leq$ 1% (%)	Feas. (%)	Gap (%)	Time (s)	$\leq$ 1% (%)	Feas. (%)	Gap (%)	Time (s)	$\leq$ 1% (%)	Feas. (%)
Full MIP (Gurobi)	0.00	525.21	100	100	0.00	3728.82	100	100	0.00	0.14	100	100
Predict+Search	1.13	0.12	97	99	22.02	251.79	21	83	29.81	0.01	0	100
Neural Diving	1.04	1.52	99	99	1.53	398.34	65	100	2.91	1.23	5	100
ConPaS	0.95	1.03	100	100	0.02	3404.19	100	100	0.90	0.26	65	100
Linear+MIP (BCE)	4.92	0.03	20.1	100	15.81	273.60	17	100	83.99	0.02	0	100

Table 1: Main results across benchmarks (mean over test instances). We report primal gap, runtime, feasibility, and the fraction of instances achieving either exact recovery or a solution within

1\%

of the global optimum.

Figure 2: Energy vs. solution quality. Spearman $\rho$ is reported per benchmark.

Benchmark	Train $\rightarrow$ test	Primal Gap (%)	Instances $\leq 1\%$ (%)	Feasibility (%)
CART	$m=16\rightarrow 12$	0.98	63	100
CART	$m=16\rightarrow 16$	0.05	100	100
CART	$m=16\rightarrow 20$	1.23	49	100
CA	$175\rightarrow 175$	0.20	95	100
CA	$175\rightarrow 250$	0.98	69	100

Table 2: Cross-scale generalization without retraining.

				EnerGNN			Neural Diving			ConPaS
Benchmark	Constraint shift	Selected removed (%)	Hamming shift	Gap (%)	$\leq 1\%$ (%)	Feas. (%)	Gap (%)	$\leq 1\%$ (%)	Feas. (%)	Gap (%)	$\leq 1\%$ (%)	Feas. (%)
CART (facilities)	Remove 1	31.35	3.84	0.21	96.24	100	2.99	40.44	89.66	0.30	87.15	100
	Remove 2	50.81	5.27	0.34	93.27	100	4.38	25.06	72.85	0.70	77.96	99.77
	Remove 3	61.99	6.26	0.45	91.23	100	4.32	20.18	49.12	1.08	69.88	98.28
CA (bids)	Remove 5	20.30	34.87	0.21	93.36	100	3.41	9.73	100	1.13	54.09	100
	Remove 10	40.61	38.77	0.17	95.27	100	4.12	5.09	100	1.45	41.09	100

Table 3: Zero-shot constraint injection. We report the fraction of originally selected variables removed, the mean Hamming shift from the original optimum, mean primal gap, the fraction of instances within

1\%

of the modified global optimum, and feasibility.

	CART		QKP		CA
Variant	Gap (%)	$\leq$ 1% (%)	Gap (%)	$\leq$ 1% (%)	Gap (%)	$\leq$ 1% (%)
Full EnerGNN	0.05	100	0.31	99	0.53	77
No calibration loss	0.78	70	0.88	68	7.69	4
No infeasibility loss	0.06	100	0.39	99	0.58	77

Table 4: Loss ablation.

Benchmark	$\|\mathbf{y}\|$	Readout binaries	ReLU binaries	Total binaries	Continuous variables	Hard feasibility constraints	Total constraints	Inference time (s)
CART	16	4	32	52	290	1	461	1.46
QKP	150	0	32	182	292	1	389	3.56
CA	175	0	32	207	298	131.74	525.74	8.62

Table 5: Neural-MIP formulation dimensions and mean inference time across test instances. For CART, inference time excludes downstream patient scheduling.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	Label generation	Training	Total offline	Break-even instances
QKP	14.7 h	3.39 h	18.1 h	$\approx 125$
CA	0.12 h	5.54 h	5.66 h	Not reached
CART	123.2 h	3.52 h	126.72 h	$\approx 130$

Appendix

Table 6: Offline computational cost and approximate amortization break-even points.

Hyperparameter	CART	CA	QKP
Learning rate	$2\times 10^{-6}$	$1\times 10^{-6}$	$1\times 10^{-5}$
Weight decay	$1\times 10^{-5}$	$1\times 10^{-5}$	$1\times 10^{-5}$
Epochs	2000	2000	2000
$\lambda_{\mathrm{cal}}$	1.0	0.01	0.05
$\lambda_{\mathrm{inf}}$	0.1	0.1	0.1
$T$	0.1	0.2	0.5

Appendix

Table 7: Training hyperparameters for the full EnerGNN runs reported in the paper. Here

\lambda_{\mathrm{inf}}

denotes the infeasible shaping weight,

T

is the prediction softmax temperature,

\tau_{\mathrm{rank}}

is the target ranking temperature,

\delta_{\mathrm{inf}}

is the infeasible Huber transition scale.

Model component	Minimum	Maximum	Mean
Constraints	2,284,802	92,139,833	46,766,602
Binary variables	532,496	21,532,176	10,928,170
Continuous variables	1,177,490	47,445,565	24,082,020
General integer variables	8,336	336,456	170,768
Total variables	1,718,322	69,314,197	35,180,958

Appendix

Table 8: Dimensions of the complete monolithic CART formulations in the extended

m=16

test set.

Model component	Full model mean	EnerGNN-reduced mean	Reduction (%)
Constraints	46,766,602	10,819,588	76.9
Binary variables	10,928,170	2,434,726	77.7
Continuous variables	24,082,020	5,499,214	77.2
General integer variables	170,768	170,756	0.01
Total variables	35,180,958	8,104,696	77.0

Appendix

Table 9: Mean dimensions of the complete and EnerGNN-reduced CART formulations in the extended

m=16

setting.

Figure 3: Primal gap distributions for all learning-based methods. Infeasible outputs are assigned a 100% gap penalty.

Injected constraint	Primal Gap (%)	$\leq 1\%$ (%)
$\sum_{m}y_{m}\leq 6$	0.06	100
$\sum_{m}y_{m}\leq 5$	0.07	100
$\sum_{m}y_{m}\leq 4$	0.12	98
$\sum_{m}y_{m}\leq 3$	0.30	93
$y_{m_{10}}=0$	0.05	100
$y_{m_{10}}=0,\;y_{m_{13}}=0$	0.03	100

Appendix

Table 10: Additional zero-shot constraint injection results on CART.

Injected constraint	Primal Gap (%)	$\leq 1\%$ (%)
$\sum_{b}y_{b}\leq 30$	0.20	95
$\sum_{b}y_{b}\leq 20$	0.22	94
$\sum_{b}y_{b}\leq 15$	0.24	92
$\sum_{b}y_{b}\leq 10$	0.17	96
$\sum_{b}y_{b}\leq 5$	0.14	94

Appendix

Table 11: Additional zero-shot constraint injection results on CA.

Train $\rightarrow$ test	Primal Gap (%)	$\leq$ 1% (%)	Feasibility (%)
$175\rightarrow 175$	0.53	77	100
$175\rightarrow 250$	1.40	45	100

Appendix

Table 12: CA cross-scale generalization with the nonlinear energy head.

Head	Layers	ReLU binaries	Total binaries	Gap (%)	$\leq 1\%$ (%)	Time (s)
MLP-16	1	16	166	0.47	97	1.07
MLP-16	2	32	182	0.31	100	2.77
MLP-32	1	32	182	0.31	99	3.56
MLP-32	2	64	214	0.35	100	19.78
MLP-64	1	64	214	0.42	99	4.72
MLP-64	2	128	278	0.37	99	186.23

Appendix

Table 13: Energy head architecture ablation on QKP.

Head	Layers	ReLU binaries	Total binaries	Gap (%)	Time (s)
MLP-16	1	16	36	0.09	0.59
MLP-16	2	32	52	0.13	1.33
MLP-32	1	32	52	0.05	1.88
MLP-32	2	64	84	0.02	3.55
MLP-64	1	64	84	0.10	3.11
MLP-64	2	128	148	0.07	24.69

Appendix

Table 14: Energy head architecture ablation on CART.

Infeasibility loss	Mean gap (%)	Exact optimum (%)	$\leq 1\%$ (%)	Feasible (%)	Mean time (s)
Current calibration	0.20	67	95	100	0.28
Strict dominance margin	3.96	4	18	100	0.25

Appendix

Table 15: Effect of enforcing strict feasible–infeasible dominance on CA.

Problem	Readout	Mean gap (%)	Exact (%)	$\leq 1\%$ (%)	Time (s)
CA	Embedding pools only	0.20	68	95	0.25
CA	Full proposed readout	0.20	67	95	0.28
CA	Embedding pools + full $\mathbf{y}$	0.21	67	95	0.25
QKP	Selected item pool only	0.81	0	72	0.50
QKP	Full proposed readout	0.31	4	99	3.56
QKP	Selected item pool + full $\mathbf{y}$	0.94	0	61	1.17

Appendix

Table 16: Readout design ablation on CA and QKP.

Combinatorial Optimization

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

See all 386 papers

Graph neural networks and the energetic cavity method for combinatorial optimization
Sep 7, 2026Joe Bacchus George, George T. CantwellGraph Neural Networks Combinatorial Optimization
Department of Engineering, University of Cambridge, CB2 1PZ, United Kingdom
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
Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe
Sep 22, 2026Akbar Rafiey, Yifei Xu, Nikolaos KaraliasSelf-Supervised Learning Combinatorial Optimization
NYU · MIT

Sep 7, 2026J/K move · Enter open · S save

Graph neural networks and the energetic cavity method for combinatorial optimization

Joe Bacchus George, George T. Cantwell

Department of Engineering, University of Cambridge, CB2 1PZ, United Kingdom

Graph Neural Networks Combinatorial Optimization Neural Combinatorial Optimization

Open paper AskPDF arXiv

We study the use of graph neural networks (GNNs) for finding approximate ground states of Ising models. Efficiently finding these ground states is of broad significance because many combinatorial optimization problems can be formulated as an Ising model with the appropriate choice of couplings and fields. Exactly solving these problems is hard but there are many good heuristic methods. A lineage of these heuristics build from mean-field approximations: one approach uses the leading eigenvector of an appropriately defined matrix, another is the min-sum algorithm, also known as the energetic cavity method. Without modification, GNNs perform worse than both of these methods. We consider small modifications to the GNN to incorporate these heuristics and find that this considerably improves performance. While the modified approach is competitive against other deep-learning approaches, we still find that simulated annealing is reliably at least as good as deep learning methods for the same computational cost.

Abstract

Combinatorial Optimization

Explore similar work

Graph neural networks and the energetic cavity method for combinatorial optimization

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

Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe