Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs

Abstract

The effectiveness of stochastic algorithms based on Monte Carlo dynamics in solving hard optimization problems is mostly unknown. Beyond the basic statement that at a dynamical phase transition the ergodicity breaks and a Monte Carlo dynamics cannot sample correctly the probability distribution in times linear in the system size, there are almost no predictions nor intuitions on the behavior of this class of stochastic dynamics. The situation is particularly intricate because, when using a Monte Carlo based algorithm as an optimization algorithm, one is usually interested in the out of equilibrium behavior which is very hard to analyse. Here we focus on the use of Parallel Tempering in the search for the largest independent set in a sparse random graph, showing that it can find solutions well beyond the dynamical threshold. Comparison with state-of-the-art message passing algorithms reveals that parallel tempering is definitely the algorithm performing best, although a theory explaining its behavior is still lacking.

arXiv comment14 pages, 12 figures

References in corpus (19)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Parallel Tempering: Theory, Applications, and New Perspectives
• Phase Transitions in the Coloring of Random Graphs
• Clustering of solutions in the random satisfiability problem
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Learning by message-passing in networks of discrete synapses
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• The backtracking survey propagation algorithm for solving random K-SAT problems
• On independent sets in random graphs
• The hard-core model on random graphs revisited
• Comparing Beliefs, Surveys and Random Walks
• Biased landscapes for random Constraint Satisfaction Problems
• The large deviations of the whitening process in random constraint satisfaction problems
• Parallel Tempering for the planted clique problem

Cited by in corpus (11)

• Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Hard Optimization Problems have Soft Edges
• Exploring Quantum Annealing Architectures: A Spin Glass Perspective
• Revisiting the Challenges of MaxClique
• Evolutionary Monte Carlo of QM properties in chemical space: Electrolyte design
• Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Effect of constraint relaxation on dynamic critical phenomena in minimum vertex cover problem
• Interacting Copies of Random Constraint Satisfaction Problems