CS Paper Radar

Solver-Admitted Metamorphic Testing of Learned Network Optimization Surrogates

Vineet Jagadeesan Nair, Stephen Peng, Arun Ravindran

cs.AI cs.LG ·submitted 2026-11-06 00:47 UTC · v1

Abstract

Equivalent encodings of an optimization problem can produce different learned predictions. Interpreting these differences requires accounting for numerical error and multiple optima. We construct metamorphic tests for optimization solver surrogates with explicit eligibility conditions, output alignment, and numerical thresholds. Reference-solver agreement and independent constraint checks determine which sampled pairs enter the audit. We study alternating-current optimal power flow (AC-OPF), the traveling salesman problem (TSP), the capacitated vehicle routing problem (CVRP), and maximum independent set (MIS). Across five grids, GridSFM-Open violates each of 13 relations on at least one grid, and 12 by more than twice the threshold. Randomly initialized copies of the grid models fail nearly the same relations, so the failures do not require training. Source patches and input canonicalization remove selected discrepancies, but no intervention establishes preserved accuracy and feasibility within the declared margin on every grid. In routing, Policy Optimization with Multiple Optima (POMO) has a single-pass rotation/reflection violation rate that rises from 12.7% to 89.5% between 20 and 100 cities. Graph-Based Diffusion Solvers for Combinatorial Optimization (DIFUSCO) violates the MIS disjoint-union relation on 35.6% of draws. Post hoc normalization within connected components removes these violations on the tested graphs. These findings support reporting metamorphic consistency alongside optimality, feasibility, and accuracy, and validating repair quality separately from consistency.

Closest papers

Nearest neighbours by meaning across the whole index.

Metamorphic testing of learned AC optimal power flow surrogates reveals representation dependence

cs.LG cs.AIeess.SYmath.OC ·2026-11-10 ·Stephen Peng, Vineet Jagadeesan Nair
top venuecode/data similarity 0.68
Abstract · Accepted to the NeurIPS 2026 Workshops on (i) Trustworthy AI Evaluation, (ii) AI Foundations for Power Grids, (iii) Tackling Climate Change …

Evaluating a learned AC optimal power flow (AC-OPF) surrogate on one grid serialization cannot show whether its accuracy depends on that encoding. We test this dependence with thirteen metamorphic relations, each specifying when a transformation is valid and how to compare its outputs. Our audit covers 17 model and pipeline configurations: two released trained checkpoints and 15 random-weight architecture or mechanism controls. Every configuration violates at least six relations, even at reporting tolerances ten times tighter or looser. For GridSFM-Open v1.1, source inspection and intermediate-tensor interventions point to an indexing bug and three noncanonical or numerically unstable preprocessing choices; a repaired checkpoint remains untested. In a separate case500 training experiment, augmentation lowers transformed-view error in three of four models and median discrepancy and constraint-violation P95 in all four. These benefits depend on the training protocol: some relations worsen, and every evaluated prediction remains AC infeasible. A GPU/CPU eigensolver mismatch accounts for most of the large raw-Laplacian-baseline gain. We recommend reporting representation consistency alongside accuracy, feasibility, and cost. These results establish neither deployment readiness nor universal invariance.

0.45

Size Generalization for Diffusion Routing Solvers

cs.AI ·2026-10-12 ·Barak Itzchak Davidovitch, Eli Meirom, Ethan Fetaya, Gal Chechik
similarity 0.64
Abstract

Routing problems, like the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), are NP-hard and slow to solve for large instances. Diffusion-based solvers can be trained in a supervised way using sets of optimal solutions, and then quickly solve new test instances. However, for large instances, optimal solutions are hard to find, and diffusion models fail to generalize to instance sizes outside their training distribution. Here we describe ResizeCO, a label free size-generalization approach that addresses both the change in statistical properties of larger instances, and the computational challenge of solving them quickly. It uses reinforcement learning on large-scale instances to adapt a diffusion model trained on small instances. Specifically, we adapt GRPO to this problem, using route length as the training signal. ResizeCO also formulates k-opt as a tree search, solved by a beam search on the GPU. In size-generalization experiments on TSP and CVRP instances with up to 10000 nodes, ResizeCO achieves a Pareto front over route quality and time that dominates learned solvers, and also outperforms other solvers at short run times, setting a new state of the art.

0.10

Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

cs.AI ·2026-09-28 ·Jiale Zhao, Sirui Mao, Zimu Chen, Wentao Yang, Zihan Wang +3 more
similarity 0.62
Abstract · 31 pages, 5 figures

Large-scale routing problems are difficult to solve efficiently as their search spaces grow rapidly with problem size. Existing approaches primarily improve the optimization procedure itself, often at increasing computational cost. We instead shift the focus to a useful initialization that can be refined into a high-quality solution with limited downstream refinement. We propose Just Initialize, a training-free and solver-agnostic initialization component for large-scale routing optimization. Just Initialize compresses a large routing instance into a compact surrogate space, optimizes its global routing structure, and recovers the resulting solution as an optimization-friendly starting point in the original space. Extensive experiments on Traveling Salesman Problems (TSPs), Capacitated Vehicle Routing Problems (CVRPs), Vehicle Routing Problems with Time Windows (VRPTWs), and Prize-Collecting Traveling Salesman Problems (PCTSPs) demonstrate that Just Initialize achieves high-quality solutions comparable to or better than state-of-the-art methods while substantially reducing computational cost across instances ranging from 1K to 100K nodes, including an average speedup of approximately 70$\times$, sub-second runtimes on 10K-node instances, and runtimes within tens of seconds on 100K-node instances.

0.19

When Does Learned Constraint Selection Pay in Security-Constrained Optimisation? A Boundary Map from SCOPF to Unit Commitment

eess.SY cs.AI ·2026-11-11 ·Milad Kazemi, Behzad Kazemtabrizi
similarity 0.62
Abstract · 10 pages, 6 figures, 4 tables

Learning-to-optimise methods for security-constrained optimal power flow (SCOPF) predict the security constraints that bind on each instance and solve only the reduced problem, with reported speed-ups of two to four orders of magnitude over the full problem. We ask whether learned selection beats the strongest learning-free alternative: a fixed umbrella set enforcing every constraint observed to bind in training. Our criterion, the price of a spare, answers this in advance: an enforced but inactive constraint is free, so the umbrella is exactly optimal wherever feasible, and learning can pay only where a spare decision carries a price. We test it systematically, including every PGLib-OPF network up to 10,000 buses. For SCOPF on a fixed network the umbrella is never beaten: its median size is five constraints across 43 networks, with no size trend, and our selector, while reproducing speed-ups of published magnitude (about x80,000 at case500), gains at most 0.25 ms over the umbrella and violates constraints on 4-5% of instances. Configuration diversity can break the umbrella's coverage on a small, densely meshed network but not at 2,000 buses, and we certify coverage with conformal risk control. In unit commitment, where a spare has a price, a static commitment loses 4-12% out of sample, and a predict-repair-reduce pipeline recovers it (cost gap 0.2-2.9%, fully feasible, 16-161x faster than the MILP). In our experiments, whether learning pays depends not on problem size but on whether a spare carries a price.

0.25

Differentiable Electricity-Market Clearing for Gradient-Based Planning

cs.LG cs.CY ·2026-09-02 ·Luca Mungo, Maarten P. Scholl, Arnau Quera-Bofarull
similarity 0.61
Abstract · 9 pages, 4 figures

Planning a large data center is difficult because a facility big enough to matter changes the electricity prices it will pay. Those prices are set by market clearing, a constrained optimization problem solved anew in every operating condition. However, simulating the market tells a planner how a candidate plan performs but not how to improve it. Here we treat market clearing as a differentiable optimization layer: each forward pass solves the market, and reverse-mode automatic differentiation propagates the planning cost back through the cleared prices to the plan. After validating these gradients against finite differences, we apply them to a concrete problem: allocating 50 MW of data-center load across six candidate buses in two synthetic networks, under a fixed cost per active site, evaluated over 36 operating states. Judged against exhaustive enumeration of all site combinations, gradient optimization recovers the continuous allocations almost exactly, with worst-case objective gaps of 2.3\% and 8.5\% of the cost difference between the best and worst single site. Its one systematic error is instructive: near the costs at which a site should close, the smooth relaxation of the discrete site count shrinks the site rather than closing it, so discrete transitions arrive late. Differentiable market clearing thus turns market-aware planning into a problem gradients can search.

0.37

Scaling Laws for Physics-Aware ACOPF Surrogate Learning

cs.LG ·2026-09-14 ·Yijiang Li, Emon Dey, Stefano Fenu, Massimiliano Lupo Pasini, Teja Kuruganti +1 more
similarity 0.60
Abstract

Learning-based surrogates for AC optimal power flow (ACOPF) promise large speedups over classical solvers, but their operational value depends on physical feasibility as much as predictive accuracy. Physics-aware objectives such as the augmented Lagrangian (AL) improve constraint satisfaction at additional per-step cost, yet how this trade-off behaves with scale is uncharacterized. We sweep model and dataset sizes under MSE and AL training, and measure how violation changes with network size. Both objectives improve as power laws: MSE prediction loss depends more on model size than on data, while the AL composite of prediction loss and violation improves comparably along both axes. Violation grows markedly more slowly with network size under AL. On matched hardware and equal training samples, AL reduces violation about $19\times$ with $2.4\times$ the training time and negligible added memory. The training objective shapes not only where a surrogate lands but how its quality evolves with scale.

0.20

Admission Without Answers: Label-Free Certification and Experience Learning for LLM-Based Optimization Modeling

cs.AI ·2026-08-16 ·Junbo Jacob Lian, Huiling Chen, Hanzhang Qin, Chung-Piaw Teo
benchmarkcode/data similarity 0.59
Abstract · Code and data are available at https://github.com/junbolian/AdmitOR

Agents that learn from experience improve at optimization modeling by storing solved trajectories and reusing them as skills. A wrong trajectory that enters the library can be retrieved for many later problems, and a stream of new problems carries no ground-truth answers that could keep it out. Existing learners admit trajectories by matching known optima, and label-free substitutes such as execution success or agreement at one instance admit wrong models. We introduce AdmitOR, a label-free admission gate. It generates models from three model families and solves each on the stated problem and on instances with resampled parameters. It keeps the largest group of models whose optimal values agree on every instance and that spans more than one family. A threshold fitted on solver-verified problems maps this agreement to acceptance, abstention, or escalation, with a finite-sample bound on the false-discovery rate of accepted values. Inside a recent skill learner, AdmitOR raises admission precision from 0.871 under majority vote to 0.927. Its library is the smallest of the four compared and has the highest macro accuracy on five benchmarks. An ablation traces the gain to an accepted value external to the learner. One program from the learner's own model already raises precision to 0.923, and agreement across families raises it further. With one candidate per family, resampling can withhold a certificate but cannot change its value, and the values it withholds are wrong far more often than those it keeps, on the stream and on the solver-verified calibration set. The false-discovery bound holds on the calibration set but not on the benchmark stream. An audit traces every false certificate to a benchmark text that omits or rounds the numbers needed to reproduce the labeled answer, or to a label error. A label-free check of the extracted numbers against the text flags most omitted-number cases.

0.54

Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

cs.LG ·2026-08-14 ·Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov
published similarity 0.59
Abstract

The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.

0.22