Solver-Admitted Metamorphic Testing of Learned Network Optimization Surrogates
Organizations: AI Science Institute, Boston Consulting Group
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.
Figures & tables
| Relation | Tier | Transform | Pull-back | Eligibility |
|---|---|---|---|---|
| R0 component labels | A | permute generator, load and shunt identifiers | inverse relabeling | always |
| R1 bus labels | A | permute bus identifiers and remap every incidence | inverse relabeling | always |
| R2 row order | A | reorder the rows of an edge table | identity | always |
| R3 branch direction | A | swap a branch’s ends and charging, negate and swap angle bounds | identity on nodes | tap , shift exactly |
| tap-side-flip | A | refer a transformer to its other side ( , impedance and charging rescaled) | identity on nodes | complement of R3’s domain |
| ref-bus-move | A | move the angle reference within an island | re-anchor at the original | see reference rules |
| Relation | Tier | Transform | Pull-back |
|---|---|---|---|
| TSP: Concorde, certified optimum | |||
| M1 | A | permute the cities | relabel the tour |
| M2 | A | rotate or reflect the square | identity |
| M3 | B | add a coincident copy of a city | drop the copy |
| M4 | B | add the rounded midpoint of an optimal-tour edge | drop the midpoint |
| M5 | C | scale coordinates by 0.5 or 0.25 | identity |
Metamorphic Testing
Metamorphic testing checks whether outputs change predictably across related inputs, providing test oracles when exact expected answers are unavailable.
See all 24 papers