Solved at Scale

Cross-Checking the Optimum

A solver answer becomes a certificate only when an independent computation agrees. This repo's own exact brute-force enumeration checks every candidate assignment and lands on the same minimum, so the optimum is proven, not trusted.

highlighted = computed this step

Own enumeration

This repo's own exact integer arithmetic enumerates all 120 candidate assignments. Why: an independent check must not reuse the solver's code path, otherwise a shared misunderstanding would pass as agreement.

candidates=120\text{candidates}=120
cross-checked by enumeration, cost 265T1T2T3T4W190807570W235855565W3125959095W44511095115W55010090100idle

Exact agreement

The enumeration minimum is 265 and CP-SAT reported 265: exact agreement. Why: two independent computations landing on the same integer is a certificate, not a coincidence, because either side disagreeing would stop the build.

min⁡ brute=265=CP-SAT\min \text{ brute}=265=\text{CP-SAT}
cross-checked by enumeration, cost 265T1T2T3T4W190807570W235855565W3125959095W44511095115W55010090100idle

Provable optimum

Every candidate was inspected and none is cheaper, so this assignment is provably optimal by our own enumeration, not trusted because a solver said so; exactly one candidate reaches the minimum. Why: enumeration inspects every feasible matching, so no cheaper assignment can exist anywhere in the candidate set.

unique optimum, certified twice\text{unique optimum, certified twice}
cross-checked by enumeration, cost 265T1T2T3T4W190807570W235855565W3125959095W44511095115W55010090100idle

Diagram note

The highlighted assignment is the one both methods certify. The enumeration count and the minimum cost are recomputed from the matrix on every build. Pixel positions are rounded for layout; every number shown is exact.

recomputed on every build\text{recomputed on every build}
cross-checked by enumeration, cost 265T1T2T3T4W190807570W235855565W3125959095W44511095115W55010090100idle