# Compact Optimality Verification for Optimization Proxies

arXiv: https://arxiv.org/abs/2405.21023 · HTML: https://mlsanity.com/paper/2405.21023/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 51 references that are in the map.
- First posted on arXiv 31 May 2024.

## Builds on (most cited first, 30 of 40)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [End to End Learning for Self-Driving Cars](https://mlsanity.com/paper/1604.07316/) (2016)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers](https://mlsanity.com/paper/2011.13824/) (2020)
- [DC3: A learning method for optimization with hard constraints](https://mlsanity.com/paper/2104.12225/) (2021)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [General Cutting Planes for Bound-Propagation-Based Neural Network Verification](https://mlsanity.com/paper/2208.05740/) (2022)
- [Predicting AC Optimal Power Flows: Combining Deep Learning and Lagrangian Dual Methods](https://mlsanity.com/paper/1909.10461/) (2019)
- [Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound](https://mlsanity.com/paper/2205.00263/) (2022)
- [The Power Grid Library for Benchmarking AC Optimal Power Flow Algorithms](https://mlsanity.com/paper/1908.02788/) (2019)
- [Self-Supervised Primal-Dual Learning for Constrained Optimization](https://mlsanity.com/paper/2208.09046/) (2022)
- [Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach](https://mlsanity.com/paper/2009.12562/) (2020)
- [DeepOPF: A Deep Neural Network Approach for Security-Constrained DC Optimal Power Flow](https://mlsanity.com/paper/1910.14448/) (2019)
- [End-to-End Feasible Optimization Proxies for Large-Scale Economic Dispatch](https://mlsanity.com/paper/2304.11726/) (2023)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [RAYEN: Imposition of Hard Convex Constraints on Neural Networks](https://mlsanity.com/paper/2307.08336/) (2023)
- [Learning Optimization Proxies for Large-Scale Security-Constrained Economic Dispatch](https://mlsanity.com/paper/2112.13469/) (2021)
- [Learning Optimal Power Flow: Worst-Case Guarantees for Neural Networks](https://mlsanity.com/paper/2006.11029/) (2020)
- [RNA Secondary Structure Prediction By Learning Unrolled Algorithms](https://mlsanity.com/paper/2002.05810/) (2020)
- [Physics-Informed Neural Networks for Minimising Worst-Case Violations in DC Optimal Power Flow](https://mlsanity.com/paper/2107.00465/) (2021)

## Built on by (most cited first, 2 of 2)

- [Self-Certifying Primal-Dual Optimization Proxies for Large-Scale Batch Economic Dispatch](https://mlsanity.com/paper/2510.15850/) (2025)
- [DCEmbed: Scalable Optimization over Neural Surrogates](https://mlsanity.com/paper/2609.33879/) (2026)

## Abstract (arXiv)

Recent years have witnessed increasing interest in optimization proxies, i.e., machine learning models that approximate the input-output mapping of parametric optimization problems and return near-optimal feasible solutions. Following recent work by (Nellikkath & Chatzivasileiadis, 2021), this paper reconsiders the optimality verification problem for optimization proxies, i.e., the determination of the worst-case optimality gap over the instance distribution. The paper proposes a compact formulation for optimality verification and a gradient-based primal heuristic that brings substantial computational benefits to the original formulation. The compact formulation is also more general and applies to non-convex optimization problems. The benefits of the compact formulation are demonstrated on large-scale DC Optimal Power Flow and knapsack problems.