Self-Certifying Primal-Dual Optimization Proxies for Large-Scale Batch Economic Dispatch

This paper proposes a hybrid solver that combines trained primal-dual optimization proxies with classical solvers and duality theory to provide certified, interpretable speed-optimality tradeoffs, achieving over 1000x speedup on large-scale economic dispatch problems while guaranteeing a maximum optimality gap of 2%.

The Gist

Imagine you are the conductor of a massive, high-speed orchestra (the power grid). Every few minutes, you need to decide exactly how much electricity each instrument (generator) should play to meet the audience's demand, all while keeping the music in tune and not breaking any instruments (overloading power lines).

Doing this perfectly is like solving a giant, complex math puzzle. Traditionally, you'd use a super-smart, slow mathematician (a classical solver) to find the perfect answer. It's accurate, but it takes time. If you have to solve this puzzle 100,000 times a day (for risk simulations or market planning), the mathematician gets exhausted, and the concert stalls.

Recently, scientists tried using a fast AI apprentice (an optimization proxy) to guess the answers. This apprentice is incredibly fast—it can guess the solution in a blink. However, there's a catch: sometimes, the apprentice gets wildly wrong. On average, it's great, but if you ask it a tricky question, it might give an answer that is 100% off. You can't trust it with the safety of the grid because you don't know when it's going to mess up.

The New Solution: The "Self-Checking" Hybrid Team

This paper introduces a brilliant new team-up: a Hybrid Solver. Think of it as pairing the fast AI apprentice with a "Self-Checking" system that acts like a built-in lie detector.

Here is how it works, using a simple analogy:

1. The Two-Sided Coin (Primal and Dual)

In math, every optimization problem has two sides:

• The Primal (The Plan): "Here is my proposed schedule for the generators."
• The Dual (The Price Tag): "Here is the theoretical minimum cost and the value of the constraints."

Usually, the AI only learns to make the Plan. But in this paper, the AI is trained to make both the Plan and the Price Tag simultaneously.

2. The "Gap" Meter (The Lie Detector)

The magic happens when you compare the Plan and the Price Tag.

• If the Plan says the cost is \100 and the Price Tag says the best possible cost is \100, the gap is zero. The AI is perfect.
• If the Plan says \100 but the Price Tag says the best possible is \90, there is a gap.

This gap is a mathematical certificate. It tells you exactly how wrong the AI might be, without needing to know the "true" answer beforehand. It's like the AI holding up a sign that says, "I am 99% sure my answer is good," or "I am only 50% sure."

3. The Smart Switch (The Hybrid Solver)

Now, the system works like a smart traffic light:

• Green Light (Fast Lane): The AI makes a prediction, checks the "Gap Meter," and sees the error is tiny (e.g., less than 2%). It instantly releases the answer. Speed: 1,000 times faster than the old mathematician.
• Red Light (Slow Lane): The AI makes a prediction, checks the "Gap Meter," and sees the error is too big. It immediately stops, says "I'm not sure," and hands the puzzle over to the slow, super-accurate mathematician to solve it the hard way.

Why This is a Game-Changer

1. Trustworthy Speed
In the past, you had to choose between "Fast but risky" (AI) or "Slow but safe" (Mathematician). This system gives you the best of both. It uses the AI 99% of the time because the AI is usually right, but it has a safety net that catches the 1% of times the AI is wrong.

2. No "Black Box" Guessing
Old AI systems were "black boxes"—you put data in and got an answer out, with no idea if it was safe. This system is "self-certifying." It tells you, "I guarantee this answer is within 2% of perfect." If you need 0.1% accuracy, you can set the rule, and the system will only use the AI if it can meet that strict standard.

3. Real-World Impact
The researchers tested this on massive power grids (like the entire European transmission system).

• The Result: They solved 240,000 scenarios in less than a second.
• The Comparison: The old, parallelized super-solvers took over 10 minutes to do the same job.
• The Speedup: That's a 1,000x speedup while guaranteeing the answers are safe.

The Bottom Line

Imagine a delivery service that uses drones for 99% of packages because they are fast, but has a backup truck ready to instantly take over if a drone looks like it might crash. You get the speed of the drone with the safety of the truck.

This paper builds that "drone-truck" system for power grids. It allows energy companies to run massive simulations and make real-time decisions instantly, without worrying that the AI will accidentally black out the city. It bridges the gap between the speed of Artificial Intelligence and the reliability of traditional math.

Technical Summary

1. Problem Statement

Transmission Systems Operators (TSOs) must solve massive batches of parametric optimization problems (e.g., Economic Dispatch) for planning, risk analysis, and market clearing. While Machine Learning-based Optimization Proxies (surrogate models) offer inference speeds orders of magnitude faster than classical solvers, they suffer from a critical limitation: lack of worst-case performance guarantees.

• The Gap: While proxies often achieve low average optimality gaps (e.g., <1%), their *worst-case* gaps can be orders of magnitude higher (e.g., >100%), making them unreliable for safety-critical or regulated applications.
• Current Limitations: Existing solutions like Neural Network Verification (NNV) are computationally expensive and often yield overly pessimistic bounds. Warm-starting classical solvers with ML predictions offers speedups but rarely exceeds 25x and still requires solving every instance.

2. Methodology

The paper proposes a Hybrid Solver Framework that fuses the speed of data-driven proxies with the rigorous guarantees of classical optimization via Primal-Dual Duality Theory.

A. Core Concept: Self-Certifying Proxies

The framework relies on training two neural networks simultaneously:

1. Primal Proxy ($p_\alpha$): Predicts a feasible primal solution ($\hat{x}$).
2. Dual Proxy ($d_\beta$): Predicts a feasible dual solution ($\hat{y}$).

By ensuring both predictions are feasible (satisfying constraints), the system can compute the Duality Gap ($\Gamma_\theta$) online without knowing the ground truth optimal value:
$$\Gamma_\theta(\hat{x}, \hat{y}) = \text{Primal Objective}(\hat{x}) - \text{Dual Objective}(\hat{y})$$
This gap serves as a mathematical certificate of sub-optimality.

B. The Hybrid Solver Algorithm

For any given query $\theta$ and a user-defined optimality tolerance $\epsilon$:

1. Predict: Generate primal and dual solutions.
2. Certify: Compute the duality gap $\hat{g}$.
3. Decision:
   • If $\hat{g} \leq \epsilon$: Return the proxy prediction (fast path).
   • If $\hat{g} > \epsilon$: Fall back to a classical solver (e.g., Simplex/Interior Point) to find the exact optimal solution (safe path).

• Result: The system guarantees that the worst-case optimality gap never exceeds $\epsilon$, while avoiding the solver for the vast majority of "easy" queries.

C. Training Innovations

• Joint Primal-Dual Training: Instead of training proxies separately, the paper minimizes the Duality Gap directly as the loss function:
  $$\min_{\alpha, \beta} \frac{1}{|D|} \sum \Gamma_\theta(p_\alpha(\theta), d_\beta(\theta))$$
• Targeted Loss (ReLU/Hinge): To optimize for a specific tolerance $\epsilon$, the authors propose a hinge loss: $\max(\Gamma_\theta - \epsilon, 0)$. This focuses training effort specifically on the "hard" cases that would trigger the fallback solver.
• Normalization: The framework supports normalized gap calculations to ensure the $\epsilon$ threshold is meaningful relative to the problem scale.
• Feasibility Enforcement:
  • Primal: Uses a "proportional response" layer to project predictions onto the feasible set.
  • Dual: Uses Smoothed Self-Supervised Learning (S3L) or Dual Lagrangian Learning (DLL) to ensure dual feasibility.

3. Key Contributions

1. Controllable Worst-Case Guarantees: The first data-driven framework to provide user-defined worst-case optimality guarantees without expensive offline verification or architectural restrictions.
2. Self-Certifying Mechanism: Leverages LP duality to detect poor predictions online, eliminating the need for ground truth during inference.
3. Novel Training Procedure: Introduces a joint training scheme using the duality gap as a loss function, which is more stable and requires no labeled data (optimal solutions) for training.
4. Scalable Implementation: Demonstrates a complete implementation for large-scale Economic Dispatch (LP) problems.

4. Experimental Results

The authors evaluated the framework on large-scale European transmission benchmarks (PGLib) ranging from 1,354 to 9,241 buses.

• Speedup Performance:
  • The hybrid solver achieves speedups of 1,000x compared to a parallelized classical simplex solver while guaranteeing a maximum optimality gap of 2%.
  • At a 1% gap tolerance, the 9,241-bus case achieved a 925x speedup.
  • At a 0.5% gap tolerance, speedups ranged from 50x to 168x depending on the case size.
• Training Efficiency:
  • Training times were short (28 mins for 1,354 buses; ~70 mins for 9,241 buses) on a single consumer GPU.
  • The models required fewer than 7.5M parameters even for the largest case.
• Loss Function Comparison:
  • Using the ReLU/Hinge loss (targeting $\epsilon=1\%$) significantly improved performance at the 1% threshold (e.g., >1,500x speedup for 1,354 buses) compared to standard Empirical Risk Minimization (ERM), though ERM performed slightly better for extremely tight tolerances (<0.5%).

5. Significance and Impact

• Trustworthy AI in Power Systems: This work bridges the gap between the speed of AI and the safety requirements of critical infrastructure. It enables the use of ML for real-time risk analysis and market clearing where regulatory bodies require strict performance bounds.
• Operational Efficiency: By solving 99%+ of queries via proxies and only invoking classical solvers for outliers, TSOs can run massive Monte Carlo simulations or multi-year planning scenarios in minutes rather than hours/days.
• Generalizability: While demonstrated on Linear Programming (Economic Dispatch), the framework is theoretically applicable to any convex optimization problem where strong duality holds, offering a new paradigm for "Safe AI" in operations research.

In summary, the paper presents a robust, scalable, and mathematically rigorous solution to the "black box" problem of optimization proxies, enabling their deployment in high-stakes industrial applications.