EnerGNN speeds up exact solutions for hard constrained optimization
EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference
Machine Learning
Summary
Finding the best solution to problems with many yes/no choices and strict rules can be very slow using usual methods. The authors created EnerGNN, which combines a type of AI called graph neural networks with exact math solvers to quickly find good and valid solutions. EnerGNN learns to score solutions so the solver can find the best one without breaking any rules. It works well on problems like auctions and supply chains, is fast, and can handle new rules without retraining.
What this means in practice
- •For operations research teams: Find high-quality and guaranteed feasible solutions faster for complex constrained resource allocation problems in supply chains.
- •For logistics planners: Adjust delivery or production constraints on the fly and obtain exact optimal plans without retraining the planning model.
Authors
Niki Triantafyllou, Maria M. Papathanasiou
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.