Entropy inflection and invisible low-energy states: Defensive alliance example

Saad, David, Yeung, Chi Ho, Zhou, Hai-Jun and Xu, Yi-Zhi (2018). Entropy inflection and invisible low-energy states: Defensive alliance example. Physical Review Letters, 121 ,

Abstract

Lower temperature leads to a higher probability of visiting low-energy states. This intuitive belief underlies most physics-inspired strategies for addressing hard optimization problems. For instance, the popular simulated annealing (SA) dynamics is expected to approach a ground state if the temperature is lowered appropriately. Here, we demonstrate that this belief is not always justified. Specifically, we employ the cavity method to analyze the minimum strong defensive alliance problem and discover a bifurcation in the solution space, induced by an inflection point in the entropy-energy profile. While easily accessible configurations are associated with the lower-free-energy branch, the low-energy configurations are associated with the higher-free-energy branch within the same temperature range. There is a discontinuous phase transition between the high-energy configurations and the ground states, which generally cannot be followed by SA. We introduce an energy-clamping strategy to obtain superior solutions by following the higher-free-energy branch, overcoming the limitations of SA.

Publication DOI: https://doi.org/10.1103/PhysRevLett.121.210602
Divisions: Engineering & Applied Sciences > Mathematics
Engineering & Applied Sciences > Systems analytics research institute (SARI)
Additional Information: © 2018 American Physical Society. Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example Yi-Zhi Xu, Chi Ho Yeung, Hai-Jun Zhou, and David Saad Phys. Rev. Lett. 121, 210602 – Published 21 November 2018
Full Text Link:
Related URLs: https://journal ... Lett.121.210602 (Publisher URL)
Published Date: 2018-11-21
Authors: Saad, David ( 0000-0001-9821-2623)
Yeung, Chi Ho
Zhou, Hai-Jun
Xu, Yi-Zhi

Download

[img]

Version: Accepted Version

| Preview

[img]

Version: Accepted Version

| Preview

Export / Share Citation


Statistics

Additional statistics for this record