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× 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)
≤ 1% (%)
Feas. (%)
Gap (%)
Time (s)
≤ 1% (%)
Feas. (%)
Gap (%)
Time (s)
≤ 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 ρ is reported per benchmark.
Benchmark
Train → test
Primal Gap (%)
Instances ≤1% (%)
Feasibility (%)
CART
m=16→12
0.98
63
100
CART
m=16→16
0.05
100
100
CART
m=16→20
1.23
49
100
CA
175→175
0.20
95
100
CA
175→250
0.98
69
100
Table 2: Cross-scale generalization without retraining.
EnerGNN
Neural Diving
ConPaS
Benchmark
Constraint shift
Selected removed (%)
Hamming shift
Gap (%)
≤1% (%)
Feas. (%)
Gap (%)
≤1% (%)
Feas. (%)
Gap (%)
≤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 (%)
≤ 1% (%)
Gap (%)
≤ 1% (%)
Gap (%)
≤ 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
∣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
≈125
CA
0.12 h
5.54 h
5.66 h
Not reached
CART
123.2 h
3.52 h
126.72 h
≈130
Appendix
Table 6: Offline computational cost and approximate amortization break-even points.
Hyperparameter
CART
CA
QKP
Learning rate
2×10−6
1×10−6
1×10−5
Weight decay
1×10−5
1×10−5
1×10−5
Epochs
2000
2000
2000
λcal
1.0
0.01
0.05
λ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 λinf denotes the infeasible shaping weight, T is the prediction softmax temperature, τrank is the target ranking temperature, δ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 (%)
≤1% (%)
∑mym≤6
0.06
100
∑mym≤5
0.07
100
∑mym≤4
0.12
98
∑mym≤3
0.30
93
ym10=0
0.05
100
ym10=0,ym13=0
0.03
100
Appendix
Table 10: Additional zero-shot constraint injection results on CART.
Injected constraint
Primal Gap (%)
≤1% (%)
∑byb≤30
0.20
95
∑byb≤20
0.22
94
∑byb≤15
0.24
92
∑byb≤10
0.17
96
∑byb≤5
0.14
94
Appendix
Table 11: Additional zero-shot constraint injection results on CA.
Train → test
Primal Gap (%)
≤ 1% (%)
Feasibility (%)
175→175
0.53
77
100
175→250
1.40
45
100
Appendix
Table 12: CA cross-scale generalization with the nonlinear energy head.
Head
Layers
ReLU binaries
Total binaries
Gap (%)
≤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 (%)
≤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.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
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.
Joe Bacchus George, George T. Cantwell
Department of Engineering, University of Cambridge, CB2 1PZ, United Kingdom
Mixed-integer linear programming (MILP) is a foundational framework for combinatorial optimization across science and engineering, but remains hard to solve at scale due to NP-hardness. Recent learning-based methods typically model MILP instances as variable-constraint bipartite graphs and use Graph Neural Networks (GNNs) for representation learning, yet their locality limits representation power. We propose an attention-driven neural backbone that adopts an element-centric view of variables and constraints, with dual attention performing parallel intra-type self-attention and inter-type cross-attention. Across three representative tasks at the instance, element, and solving-state levels, our model consistently outperforms conventional GNN-based architectures, highlighting attention-based, element-centric modeling as a powerful foundation for learning-enhanced combinatorial optimization.
Peixin Huang, Yaoxin Wu, Yining Ma +3
Shenzhen Research Institute, Shandong University, China
Self-supervised learning for combinatorial optimization has emerged as a promising paradigm for solving discrete optimization problems with neural networks, but a central challenge remains: handling hard combinatorial constraints within continuous, gradient-based training. Continuously extending combinatorial objectives to convex domains is a powerful technique, yet existing approaches often require projection steps that constrain neural network outputs to lie inside the feasible polytope and rely on ad-hoc and problem-specific constructions. We propose a general framework in which the neural network is allowed to predict arbitrary continuous vectors that could potentially lie outside of the feasible polytope. These predictions are then approximated by sparse convex combinations of feasible solutions using a geometric decomposition algorithm based on Frank--Wolfe methods and approximate Caratheodory results. This decomposition induces an a.e.-differentiable, self-supervised loss defined as the expected value of the discrete objective. The same procedure provides an automatic rounding guarantee at inference time. We demonstrate strong empirical performance across multiple combinatorial problems, including the Quadratic Assignment Problem, Maximum Coverage, and the Traveling Salesperson Problem.