Entropy Inflection and Inaccessible Ground States: the Defensive Alliance Example

Abstract

Lower temperature leads to a higher probability of visiting low-energy states. This intuitive belief is underlying most physics-inspired strategies for hard optimization problems. For instance, the popular simulated annealing (SA) is expected to approach a ground state if the temperature is dropped appropriately. Here we demonstrate that this belief is not always justified. Specifically, we employ the cavity method to the hard computational problem of minimum strong defensive alliance to discover a bifurcation in the solution space, induced by an inflection point in the entropy--energy profile. While SA follows the lower-free-energy but far-from-optimal branch, ground-state solutions are obtained by following the higher-free-energy branch within the same temperature range. The existence of an inflection point causes the anomalous behavior of energy decreasing with temperature and makes the ground states inaccessible. We introduce an energy-clamping strategy to obtain superior solutions following the higher-free-energy branch, overcoming the limitations of SA.