Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example

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.

arXiv comment18 pages (including main text and appendices). The simulated annealing algorithm extensively revised, and discontinuous phase transition discussed

References in corpus (23)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Simulated Tempering: A New Monte Carlo Scheme
• Statistical mechanics and dynamics of solvable models with long-range interactions
• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• A Landscape Analysis of Constraint Satisfaction Problems
• Reconstruction on trees and spin glass transition
• Glass models on Bethe lattices
• Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels
• Microcanonical entropy inflection points: Key to systematic understanding of transitions in finite systems
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Finding One Community in a Sparse Graph
• Classification of Phase Transitions by Microcanonical Inflection-Point Analysis
• Statistical Mechanics of systems with long range interactions
• Belief propagation for graph partitioning
• Metastable states of a ferromagnet on random thin graphs
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Metastable configurations on the Bethe lattice
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• Self-sustained Clusters and Ergodicity Breaking in Spin Models
• Self-Sustained Clusters as Drivers of Computational Hardness in $p$-spin Models
• Slow Spin Dynamics and Self-Sustained Clusters in Sparsely Connected Systems

Cited by in corpus (8)

• Pre-Cooling Strategy Allows Exponentially Faster Heating
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Kinked Entropy and Discontinuous Microcanonical Spontaneous Symmetry Breaking
• Vulnerability and Resilience of Social Engagement: Equilibrium Theory
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Ground state interface exponents of the diluted Sherrington-Kirkpatrick spin glass
• Statistical Mechanics of the L-Distance Minimal Dominating Set problem