Bifurcations in mean-field-theory annealing

Masa-aki Sato, Shin IshiiPhysical 1996 · DOI

Abstract

In this paper, we investigate bifurcation processes for the mean-field-theory (MFT) annealing applied to traveling-salesman problems (TSPs). Due to the symmetries of the TSP free energy function, some special bifurcations occur: cyclic symmetry breaking bifurcations and reverse symmetry breaking bifurcations. Saddle-node bifurcations also occur. Which type of bifurcation occurs depends on the symmetry of the eigenvector that corresponds to the zero eigenvalue mode of the free energy curvature matrix at the bifurcation point. In the MFT annealing process, a sequence of bifurcations occurs and the bifurcation structure affects the quality of the annealing solution. It is shown that the annealing solution in this process is not unique in general, and it is not always the optimal solution. Our approach can also be applied to the Potts spin model and its bifurcation structure is almost the same as that of the MFT. The practical implications of our results are also discussed. \textcopyright{} 1996 The American Physical Society.
BibTeX
@inproceedings{sato1996bifurcations,
  author = {Masa-aki Sato and Shin Ishii},
  title = {{Bifurcations in mean-field-theory annealing}},
  booktitle = {Physical},
  year = {1996},
  doi = {10.1103/physreve.53.5153},
}

Loading related content...

Figure