Appears in collection : French Japanese Conference on Probability and Interactions

Combinatorial optimization problems are ubiquitous in various fields of practical and theoretical interest. The famous traveling salesman problem is one of them. One approach to tackle those problems is to use an Ising model whose Hamiltonian $H$ takes its minimum at a spin configuration, called a ground state, which corresponds to an optimal solution to the corresponding original problem. Standard MCMC methods, such as the Glauber dynamics and the Metropolis algorithm, have been used for decades to sample the Gibbs distribution, which is proportional to $e^{-H/T}$, hence close to the uniform distribution over the ground states when the temperature $T$ is very small. However, those MCMC methods are based on single-spin flip rules, hence prone to being slow. In this talk, I will explain three other MCMC methods, two among which are based on multi-spin flip rules, hence potentially fast. I will show several mathematical results, as well as numerical results to compare which is better in which context. This talk is based on joint work with Bruno Hideki Fukushima-Kimura and many others involved in the CREST project for the past five years.