Comparison Benchmarks — vs. Exact Solvers
How close does max-div get to provably optimal solutions, and what does proving
optimality cost? This page anchors the heuristic quality numbers to exact references
(CP-SAT and SCIP), on the built-in benchmark problems.
Protocol
- max-div runs the same wall-clock budget ladder as the
heuristics comparison (2× steps from 1 ms,
SMARTpreset, 3 seeds). - Exact max-min reference: CP-SAT via threshold binary search over the distinct pairwise distances (the max-min optimum is always one of them), one worker for determinism, 120 s cap. Gaps are only reported where optimality was certified.
- Exact mean/geomean reference: the nearest-neighbor assignment model (Lei–Church style), on both SCIP and CP-SAT backends. As shown below, no backend certifies it at the generators' sizes, so no mean/geomean gap-to-optimum is published — an incumbent-at-budget comparison is shown instead, clearly labeled as uncertified.
- Hardware: 16" MacBook Pro with M3-class CPU, single sequential run.
- Reproduce with
uv run --group benchmarks python -m benchmarks.tier1.full(results), then... -m benchmarks.tier1.report(tables).
Max-min: gap to the proven optimum
CP-SAT certifies the max-min optimum up to n = 300 within the cap (the proof cliff sits around n = 400; constraints help — they prune the conflict graph). max-div's gap to the certified optimum, mean over 3 seeds:
| problem | n | k | m | optimum | proof time | gap @0.016s | gap @0.128s | gap @1.024s | gap @16.384s |
|---|---|---|---|---|---|---|---|---|---|
| U1 | 100 | 10 | 0 | 0.0997 | 0.24 s | 5.7% | 5.7% | 5.6% | 3.1% |
| U1 | 200 | 20 | 0 | 0.2306 | 0.32 s | 10.7% | 9.6% | 7.6% | 7.0% |
| U1 | 300 | 30 | 0 | 0.3549 | 10.46 s | 15.1% | 11.3% | 10.2% | 6.5% |
| C1 | 100 | 10 | 2 | 0.8815 | 0.12 s | 11.0% | 6.5% | 0.0% | 0.0% |
| C1 | 200 | 20 | 4 | 0.5127 | 0.46 s | 11.8% | 6.7% | 6.7% | 3.6% |
| C1 | 300 | 30 | 6 | 0.3970 | 1.34 s | 17.1% | 9.1% | 9.1% | 6.7% |
Reading: max-div lands within roughly 10 % of the proven optimum in ~100 ms and ~3–8 % at the ladder top, occasionally hitting the optimum exactly — while the exact solver needs up to seconds-to-minutes to certify, and stops certifying entirely a factor ~2 above these sizes. Note max-min is the harshest gap measure: the objective is the single worst pair, so one suboptimal swap shows in full.
Mean/geomean: why there is no gap-to-optimum
The canonical exact formulation for mean/geomean-of-NN separation is the NN-assignment model. Its proofs stop far below the generators' smallest problem (n = 100), whichever backend runs it — time to certified optimality on a d=4 random family (k = n/10, geomean; each backend stops at its first timeout):
| n | k | SCIP (1 thread) | CP-SAT (1 worker) | CP-SAT (8 workers) |
|---|---|---|---|---|
| 40 | 4 | 36.9 s | 1.2 s | 0.8 s |
| 50 | 5 | 66.3 s | 5.8 s | 2.2 s |
| 60 | 6 | 38.2 s | 124.5 s | 10.5 s |
| 70 | 7 | 176.2 s | 3499.2 s | 38.4 s |
| 80 | 8 | 317.7 s | timeout | 159.4 s |
| 90 | 9 | timeout | — | 886.3 s |
| 100 | 10 | — | — | timeout |
CP-SAT with 8 parallel workers is the strongest backend and still times out at n = 100 (cap 1 h; the trend suggests ~2 h would be needed, and n = 110+ is out of reach). The model's closest-assignment constraints relax weakly, so cost grows ~4–5× per +10 items — this is a property of the formulation, not of any solver. Hence: no certified mean/geomean optimum exists at any published problem size.
Geomean: incumbent-at-budget comparison (uncertified)
What a practitioner can still ask: "what if I just gave a MIP/CP solver a big time budget and took its best solution?" Below, CP-SAT (8 workers) runs the assignment model at a generous cap on two shipped problems, and its incumbent — best solution found, no optimality certificate; the bound gap column shows how far the proof remained — is compared against max-div's 1-second ladder rung:
| problem | n | k | m | CP-SAT cap | CP-SAT incumbent | bound gap | max-div @~1 s (best seed) |
|---|---|---|---|---|---|---|---|
| U3 | 100 | 10 | 0 | 10800 s | 0.9915 | 338% | 0.9847 |
| C4 | 150 | 10 | 3 | 900 s | 0.4612 | 543% | 0.4612 |
On the unconstrained problem (U3), max-div reaches within ~1 % of the exact solver's 3-hour incumbent in one second. On the constrained problem (C4), max-div's 1-second solution matches the one the exact solver reached in 15 minutes (neither certified optimal). These are point comparisons on two problems, not certified gaps — but they answer the budget-parity question the certified experiment cannot reach: given comparable or far greater time, the exact solver does not pull ahead on these instances.