Research map / Optimization / Nonconvex and smooth optimization
Compact Optimality Verification for Optimization Proxies
Read the paperCheck your idea against 108,967 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 a compact MIP formulation for verifying the worst-case optimality gap of optimization proxies (which applies to non-convex problems), plus a gradient-based primal heuristic (PGA-VFA) using piecewise-linear convex value function approximation, evaluated on DC-OPF and knapsack proxies.
Problem
Verifying the worst-case optimality gap of optimization proxies over an instance distribution; existing bilevel/KKT-based formulations are computationally heavy and only apply to convex lower-level problems.
Approach
Replace the bilevel lower-level optimization with a high-point relaxation: maximize proxy cost minus cost of any feasible y in Y(x), which the paper proves has the same optimum; add a projected gradient attack that uses a convex piecewise-linear value function approximation built from dual solutions of historical instances.
Key results
- Compact formulation yields up to 209.5% speedup over the bilevel formulation on solved 300-bus instances and fewer binary variables (e.g., 1353 vs 7281 on 1354-bus).
- On open 1354-bus instances, compact formulation improves primal bounds by 282% to 657% over bilevel (e.g., 360.03K vs 94.22K$ at u=0).
- PGA-VFA finds a 562348.33 objective in 7.09s on 300-bus with 1% perturbation, while Gurobi on compact MILP takes 166.01s to reach 564263.39.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the bilevel formulation with the compact formulation | DC-OPF optimality verification · IEEE 300-bus, u=2% | solving time (s): 1302.7 -> 420.8 | Helped |
| replace the bilevel formulation with the compact formulation | DC-OPF optimality verification · IEEE 57-bus, u=1% | solving time (s): 0.6 -> 0.6 | No clear effect |
| replace the bilevel formulation with the compact formulation | DC-OPF optimality verification · IEEE 300-bus, u=10% | primal bound (K$): 466.76 -> 596.98 | Helped |
| replace the bilevel formulation with the compact formulation | DC-OPF optimality verification · IEEE 1354-bus, u=0% | primal bound (K$): 94.22 -> 360.03 | Helped |
| use PGA-VFA to find a feasible solution instead of relying on the compact solver's reference-load warm start | IEEE 300-bus DC-OPF verification · u=1% | time to objective at least as good as PGA-VFA (s): 7.09 s vs 114.79 s | Helped |
| warm-start Compact with the PGA-VFA solution instead of the reference load | Compact DC-OPF verification · IEEE 1354-bus, u=0% | objective ($): 360031.97 -> 380757.88 | Helped |
| apply compact optimality verification to a non-convex knapsack proxy | Knapsack proxy · 10 items, u=20% | optimality gap (%): 0.0 | Helped |
| increase the knapsack size and input-domain range | Compact knapsack verification · 50 items, u=20% | optimality gap (%): 0.0 -> 142.0 | Hurt |
| increase the input-domain range | Compact knapsack verification · 80 items | optimality gap (%): 0.0 -> 230.0 | Hurt |
Surprising findings
- Gurobi struggles to find primal-feasible solutions without a warm start, so the reference load is passed as warm start.
- On the 1354-bus system, the compact MILP cannot match PGA-VFA's primal quality within 6 hours.
Limitations
- Exact MIP-based verification scales poorly to large networks and deep networks with large input domains.
- Current exact verification tools mainly support ReLU networks; MIP solvers are the only option for general optimality verification constraints.
- Open instances (300-bus with large u and all 1354-bus) remain unsolved to optimality within 6 hours.
Experimental setup
Datasets: PGLib IEEE 57/118/300-bus and Pegase 1354-bus test cases (load-perturbed instances) randomly generated knapsack instances
Benchmarks: DC-OPF optimality verification on PGLib 57/118/300/1354-bus knapsack optimality verification with 10/50/80 items
Metrics: solving time model size (variables, constraints) primal objective dual bound optimality gap shifted geometric mean
Baselines: Bilevel formulation (KKT single-level) Gurobi warm-started with nominal load
Builds on: bilevel optimality verification (Nellikkath & Chatzivasileiadis, 2021) projected gradient attack optimization-based bound tightening self-supervised learning for DC-OPF proxies
Closest papers by meaning
- OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling (ICLR 2025 · similarity 0.84)
- On Traceability in $\ell_p$ Stochastic Convex Optimization (NeurIPS 2025 · similarity 0.83)
- Inverse Optimization via Learning Feasible Regions (ICML 2025 · similarity 0.83)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.83)
- Finding Simple Proofs for First-Order Optimization (NeurIPS 2026 · similarity 0.83)
- A Generalization Result for Convergence in Learning-to-Optimize (ICML 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.