Title: Patch-planting spin-glass solution for benchmarking,
Abstract: We introduce an algorithm to generate (not solve) spin-glass instances with
planted solutions of arbitrary size and structure. First, a set of small
problem patches with open boundaries is solved either exactly or with a
heuristic, and then the individual patches are stitched together to create a
large problem with a known planted solution. Because in these problems
frustration is typically smaller than in random problems, we first assess the
typical computational complexity of the individual patches using population
annealing Monte Carlo, and introduce an approach that allows one to fine-tune
the typical computational complexity of the patch-planted system. The scaling
of the typical computational complexity of these planted instances with various
numbers of patches and patch sizes is investigated and compared to random
instances.