Research map / Learning theory and algorithms / Combinatorial and search optimization
EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference
Niki Triantafyllou, Maria Papathanasiou
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes EnerGNN, a learned energy over binary configurations trained with optimality-aware contrastive learning so that a MIP layer can enforce hard constraints exactly at inference.
Problem
Constrained combinatorial inference where hard constraints and deployment-time restrictions must be satisfied exactly, which learned models typically fail to guarantee.
Approach
Learn an energy function over binary configurations that is compatible with a mixed-integer programming layer, shaping the energy landscape with optimality-aware contrastive learning so that constraints are enforced exactly at inference time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace linear energy head with ReLU MLP head (ablation) | EnerGNN · QKP | mean primal gap (%): 26.87 -> 0.31 | Improved |
| replace linear energy head with ReLU MLP head (ablation) | EnerGNN · CART | mean primal gap (%): 21.80 -> 0.05 | Improved |
| replace linear energy head with ReLU MLP head (ablation) | EnerGNN · CA | mean primal gap (%): 0.20 -> 0.53 | Hurt |
| add calibration loss (ablation) | EnerGNN · CART | mean primal gap (%): 0.78 -> 0.05 | Improved |
| add calibration loss (ablation) | EnerGNN · CA | mean primal gap (%): 7.69 -> 0.53 | Improved |
| add calibration loss (ablation) | EnerGNN · QKP | instances within 1% (%): 68 -> 99 | Improved |
| add infeasibility loss (ablation) | EnerGNN · CART, QKP, CA | mean primal gap (%): 0.06 -> 0.05 (CART) | No clear effect |
| optimize learned energy under MIP instead of restricting search (vs ConPaS) | EnerGNN · CART | time (s): 3404.19 -> 214.03 | Improved |
| transfer trained model to different size without retraining | EnerGNN · CART m=16 to 12 and 20 | mean primal gap (%): 0.05 -> 0.98 (m=12), 1.23 (m=20) | Hurt |
| increase CA bids from 175 to 250 at test time without retraining | EnerGNN (Linear) · CA | mean primal gap (%): 0.20 -> 0.98 | Hurt |
| zero-shot constraint injection (deactivate 3 facilities) | EnerGNN · CART | mean primal gap (%): 0.21 -> 0.45 (remove 1 to 3) | Hurt |
| zero-shot constraint injection vs Neural Diving | Neural Diving · CART remove 3 facilities | feasibility (%): 49.12 feasibility | Hurt |
Closest papers by meaning
- Solving Constrained Combinatorial Optimisation Problems via MAP Inference without High-Order Penalties (AAAI 2017 · similarity 0.86)
- Learning Iterative Reasoning through Energy Diffusion (ICML 2024 · similarity 0.85)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.84)
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization (ICML 2024 · similarity 0.84)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.84)
- Generalizable Reasoning through Compositional Energy Minimization (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
