  Finding an energy minimum in the Ising model is an exemplar objective,
associated with many combinatorial optimization problems, that is
computationally hard in general, but occurs in all areas of modern science.
There are several numerical methods, providing solution for the medium size
Ising spin systems. However, they are either computationally slow and badly
parallelized, or do not give sufficiently good results for the large systems.
In this paper, we present a highly parallel algorithm, called Mean-field
Annealing from a Random State (MARS), incorporating the best features of the
classical simulated annealing (SA) and Mean-Field Annealing (MFA) methods. The
algorithm is based on the mean-field descent from a randomly selected
configuration and temperature. Since a single run requires little computational
effort, the effectiveness can be achieved by massive parallelisation. MARS
shows excellent performance both on the large Ising spin systems and on the set
of exemplary maximum cut benchmark instances in terms of both solution quality
and computational time.
