Compact Optimality Verification for Optimization Proxies

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 significant 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.

Authors

• Wenbo Chen 0001
• Haoruo Zhao
• Mathieu Tanneau
• Pascal Van Hentenryck

Keywords

No keywords are indexed for this paper.