EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference
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× 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.
Related
- Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation
- Extensions of several famous combinatorial identities via hypergeometric functions
- On Sparse Graph Limits for Neural Combinatorial Optimization
- Combinatorial identities derived from explicit formulas of Gauss hypergeometric functions
- Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks
BibTeX
@misc{triantafyllou2026energnn,
title = {{EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference}},
author = {Niki Triantafyllou and Maria M. Papathanasiou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33930},
eprint = {2610.33930},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33930},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference
AU - Niki Triantafyllou
AU - Maria M. Papathanasiou
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33930
UR - https://arxiv.org/abs/2610.33930
AB - 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.
ER -