Aller au contenu

Relaxations semi-définies sur plateaux jouets : un résultat négatif

Sur des plateaux jouets générés, une relaxation semi-définie de l'appariement des arêtes est certifiée propre sur trois plateaux 5x5, indécidée sur un et inexacte sur un autre ; elle ne tient pas en 16x16 et n'a donné aucune lecture en 6x6. Sa forme de rang faible trouve bien des solutions, mais comme une recherche aléatoire que le recuit simple bat en coût. Rien ici n'est un progrès sur Eternity II.

par Raphaël Anjou

expérienceimpassemesuréréfutéMéthodes exactesRéduire la rechercheRecherche localeMis à jour 2026-11-14
Reproduirestochastique : ne se reproduit pas exactement ; le plateau est vérifiablerevérifie un plateau enregistréBudget: 5x5 convex solves 400 to 1,100 s each; 6x6 low-rank batches 30 CPU minutes per start
Matériel & exécution
Exécution nativeCPU seul
0.28cœurs·heure
Cœurs
10
RAM
32 GiB
GPU
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
Départ
toy boards from the project's painter, seeds 0 to 4; annealing and low-rank starts are random
Vérifier le plateau enregistré

stochastique : ne se reproduit pas exactement ; le plateau est vérifiable

Ceci vérifie le plateau, pas la recherche qui l'a produit.

just experiments relaxation-small-boards

Simples essais de fumée : une résolution convexe en 4x4, deux départs de rang faible sur un jouet 5x5 et un court recuit sur un jouet 6x6, chacun en moins de deux minutes. La commande ne reproduit aucun tableau de cette page ; les lots 6x6 (30 minutes CPU par départ) et les résolutions convexes 5x5 n'y sont pas, et ce sont les comptes, pas les trajectoires, qui doivent se reproduire.

Continuer l'exploration

Cité par

Source de la pageVersion Markdown