Skip to content

Semidefinite relaxations on toy boards: a negative result

On generated toy boards, a semidefinite relaxation of edge matching is certified clean on three 5x5 boards, undecided on one and not exact on one; it cannot run at 16x16 and gave no reading at 6x6. A low-rank form of it does find solutions, but as a randomised search that plain annealing beats on cost. Nothing here is Eternity II progress.

by Raphaël Anjou

experimentdead endmeasuredrefutedExact methodsReduce the searchLocal searchUpdated 2026-11-14
Reproducestochastic: won't reproduce exactly; the board is verifiablere-verifies a stored boardBudget: 5x5 convex solves 400 to 1,100 s each; 6x6 low-rank batches 30 CPU minutes per start
Hardware & run
Native runCPU only
0.28core-hours
Cores
10
RAM
32 GiB
GPUs
0
Machine
10-core Apple M4 laptop, 32 GB; 14-core low-power x86 laptop; 8-core Apple M1 (annealing timings)
Budget
5x5 convex solves 400 to 1,100 s each; 6x6 low-rank batches 30 CPU minutes per start
Start
toy boards from the project's painter, seeds 0 to 4; annealing and low-rank starts are random
Verify the stored board

stochastic: won't reproduce exactly; the board is verifiable

This verifies the board, not the search that produced it.

just experiments relaxation-small-boards

Smoke runs only: one 4x4 convex solve, two low-rank starts on a 5x5 toy and a short annealing run on a 6x6 toy, each under two minutes. It does not reproduce any table on this page; the 6x6 batches (30 CPU minutes per start) and the 5x5 convex solves are not in it, and counts, not trajectories, are what should reproduce.

Keep exploring

Referenced by

Page sourceView as Markdown