Statistical mechanics methods and phase transitions in optimization problems
From MaRDI portal
Abstract: Recently, it has been recognized that phase transitions play an important role in the probabilistic analysis of combinatorial optimization problems. However, there are in fact many other relations that lead to close ties between computer science and statistical physics. This review aims at presenting the tools and concepts designed by physicists to deal with optimization or decision problems in an accessible language for computer scientists and mathematicians, with no prerequisites in physics. We first introduce some elementary methods of statistical mechanics and then progressively cover the tools appropriate for disordered systems. In each case, we apply these methods to study the phase transitions or the statistical properties of the optimal solutions in various combinatorial problems. We cover in detail the Random Graph, the Satisfiability, and the Traveling Salesman problems. References to the physics literature on optimization are provided. We also give our perspective regarding the interdisciplinary contribution of physics to computer science.
Recommendations
- Phase Transitions in Combinatorial Optimization Problems
- An asymptotical study of combinatorial optimization problems by means of statistical mechanics
- scientific article; zbMATH DE number 4133843
- Application of statistical mechanics to NP-complete problems in combinatorial optimisation
- Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
Cites work
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
- A physicist's approach to number partitioning
- A threshold for unsatisfiability
- Application of statistical mechanics to NP-complete problems in combinatorial optimisation
- Branch-and-Bound Methods: A Survey
- Complexity of learning in artificial neural networks
- Computer Solutions of the Traveling Salesman Problem
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Cut Size Statistics of Graph Bisection Heuristics
- Determining computational complexity from characteristic ``phase transitions
- Entropy of theK-Satisfiability Problem
- Exact solution of the random bipartite matching model
- Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
- Graph bipartitioning and statistical mechanics
- scientific article; zbMATH DE number 437557 (Why is no real title available?)
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3856167 (Why is no real title available?)
- scientific article; zbMATH DE number 3904630 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256700 (Why is no real title available?)
- scientific article; zbMATH DE number 1273988 (Why is no real title available?)
- scientific article; zbMATH DE number 1082106 (Why is no real title available?)
- scientific article; zbMATH DE number 1163496 (Why is no real title available?)
- scientific article; zbMATH DE number 1544178 (Why is no real title available?)
- scientific article; zbMATH DE number 1369843 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 871931 (Why is no real title available?)
- scientific article; zbMATH DE number 956863 (Why is no real title available?)
- scientific article; zbMATH DE number 964350 (Why is no real title available?)
- scientific article; zbMATH DE number 3193293 (Why is no real title available?)
- scientific article; zbMATH DE number 3076589 (Why is no real title available?)
- Length of prime implicants and number of solutions of random CNF formulae
- Martingale Inequalities and NP-Complete Problems
- On the solution of traveling salesman problems
- On the Travelling Salesperson Problem in Many Dimensions
- Optimization by simulated annealing
- Optimization problems and replica symmetry breaking in finite connectivity spin glasses
- Phase coexistence and finite-size scaling in random combinatorial problems
- Phase transitions and the search problem
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Rigorous low-temperature results for the mean field p-spins interaction model
- Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
- The complexity of theorem-proving procedures
- The scaling window of the 2-SAT transition
- The stochastic traveling salesman problem: finite size scaling and the cavity prediction
- Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
- Tricritical points in random combinatorics: the -SAT case
Cited in
(54)- Generalized satisfiability problems: Minimal elements and phase transitions.
- Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
- Applicability of \(n\)-vicinity method for calculation of free energy of Ising model
- Dual mean field search for large scale linear and quadratic knapsack problems
- Notes on computational-to-statistical gaps: predictions using statistical physics
- Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT
- Posterior agreement for large parameter-rich optimization problems
- Phase transitions of subset sum and Shannon's limit in source coding
- Transition to coarse-grained order in coupled logistic maps: effect of delay and asymmetry
- Dual mean field annealing scheme for binary optimization under linear constraints
- The stable marriage problem: an interdisciplinary review from the physicist's perspective
- On the spectral gap of spherical spin glass dynamics
- Analytic description of the phase transition of inhomogeneous multigraphs
- Statistical mechanics of a simplified bipartite matching problem: An analytical treatment
- Global optima results for the Kauffman \(NK\) model
- New global optima results for the Kauffman \(NK\) model: Handling dependency
- A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
- Threshold properties of random Boolean constraint satisfaction problems
- An optimization algorithm inspired by the phase transition phenomenon for global optimization problems with continuous variables
- The state of SAT
- Phase transitions and the search problem
- Free energy rates for a class of very noisy optimization problems
- Configuration space analysis for optimization problems
- scientific article; zbMATH DE number 4133843 (Why is no real title available?)
- Organization mechanism and counting algorithm on vertex-cover solutions
- Local entropy as a measure for sampling solutions in constraint satisfaction problems
- Phase transitions in integer linear problems
- Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
- Statistical physics and network optimization problems
- Random instances of problems in NP -- algorithms and statistical physics
- scientific article; zbMATH DE number 4140654 (Why is no real title available?)
- Proof of the local REM conjecture for number partitioning. I: Constant energy scales
- Application of statistical mechanics to NP-complete problems in combinatorial optimisation
- Overview: PCA models and issues
- Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
- Disordered systems insights on computational hardness
- Interpolating between boolean and extremely high noisy patterns through minimal dense associative memories
- Uncovering the non-equilibrium stationary properties in sparse Boolean networks
- Phase transitions in parameter rich optimization problems
- Low temperature asymptotics of spherical mean field spin glasses
- Determining computational complexity from characteristic ``phase transitions
- Phase Transitions in Combinatorial Optimization Problems
- Polynomial combinatorial optimization methods for analysing the ground states of disordered systems
- Another look at the phenomenon of phase transition
- scientific article; zbMATH DE number 2247572 (Why is no real title available?)
- Critical properties of the SAT/UNSAT transitions in the classification problem of structured data
- Complexity of learning in artificial neural networks
- Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
- Analysis of local search landscapes for \(k\)-SAT instances
- Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble
- Replica method for computational problems with randomness: principles and illustrations
- Fourier analysis of iterative algorithms
- Spines of random constraint satisfaction problems: definition and connection with computational complexity
- Linearly constrained global optimization and stochastic differential equations
This page was built for publication: Statistical mechanics methods and phase transitions in optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958800)
