Plain language

What this result means

Negative results matter when they explain the boundary of the system. Here the benchmark is not soft: it is maintained by strong search methods, and the same operators that set the records find stable local optima. The useful output is a calibrated verifier and a map of why the table did not move.

  • The verifier reproduces downloaded archive partitions exactly, including cuts and balance.
  • The archive is closed under the simple monotonicity checks that produced free wins in other domains.
  • The report points to future soft targets but does not package any cell as a win.

Visual notes

How to read the result

Horizontal bar chart showing three Walshaw archive partition cuts reproduced exactly.
Exact reproductionsThe verifier reproduces archive cuts on known partitions. That calibrates the checker before any attack claim.
Horizontal bar chart showing zero monotonicity violations, zero ILP gain, zero verified beats, and a positive frontier gap.
No-beat routesMonotonicity checks, record-seeded refinement, and exact local search found no soft cell. The remaining frontier gaps stayed positive.

Result table

No verified beat: the archive remained match-hard under the available methods.

CellBaselineNumaroDeltaNote
3elt k=2 eps=5%8787matchedarchive partition verified
4elt k=8 eps=0%545545matchedperfect balance
whitaker3 k=32 eps=0%16681668matchedarchive partition verified
large Jet cellsarchive+1-4.5%not beatenfrontier remained out of reach

Method

How it was found

The pipeline combined archive parsing, KaHIP/KaFFPaE memetic partitioning, seeded reruns, monotonicity checks, and exact boundary-region CP-SAT refinement.

  • Rebuilt the exact Walshaw balance rule from archive tables.
  • Reproduced downloaded best partitions with an independent verifier.
  • Ran strong partitioners and exact local ILP refinement.
  • Recorded why each route matched or undershot rather than beat.

Verification

How it was checked

verify.py recomputes edge cuts and epsilon-balance directly from .graph and partition files, calibrated against archive downloads.

Scope

What is not being claimed

This is a calibration and negative-result report. It is intentionally not presented as a record win.

References

Baseline sources

Citation

How to cite

Numaro Autoresearch Team. "Walshaw graph partitioning: no record beat, useful calibration." Numaro Research Report NUMARO-CAL-2026-001, 2026.

@techreport{numaro2026WalshawGraphPartitioning,
  title = {Walshaw graph partitioning: no record beat, useful calibration},
  author = {Numaro Autoresearch Team},
  institution = {Numaro},
  number = {NUMARO-CAL-2026-001},
  year = {2026},
  url = {https://numaro.tech/research/walshaw-graph-partitioning-2026/}
}