| | Contents | |
| | | |
| |
| | List of Contributors | XI |
| 1 | Introduction
A.K. Hartmann and H. Rieger | 1 |
| Part I | Applications in Physics | 5 |
| 2 | Cluster Monte Carlo Algorithms
W. Krauth | 7 |
| 2.1 | Detailed Balance and a priori Probabilities | 7 |
| 2.2 | The Wolff Cluster Algorithm for the Ising Model | 10 |
| 2.3 | Cluster Algorithm for Hard Spheres and Related Systems | 12 |
| 2.4 | Applications | 16 |
| 2.4.1 | Phase Separation in Binary Mixtures | 16 |
| 2.4.2 | PolydisperseMixtures | 18 |
| 2.4.3 | Monomer-Dimer Problem | 19 |
| 2.5 | Limitations andExtensions | 19 |
| | References | 21 |
| 3 | Probing Spin Glasses with Heuristic Optimization Algorithms
O.C. Martin | 23 |
| 3.1 | SpinGlasses | 23 |
| 3.1.1 | Motivations | 23 |
| 3.1.2 | The Ising Model | 24 |
| 3.1.3 | Models of Spin Glasses | 24 |
| 3.1.4 | Some Challenges | 26 |
| 3.2 | Some Heuristic Algorithms | 28 |
| 3.2.1 | General Issues | 28 |
| 3.2.2 | Variable Depth Search | 32 |
| 3.2.3 | Genetic Renormalization Algorithm | 36 |
| 3.3 | Asurvey of Physics Results | 41 |
| 3.3.1 | Convergence of the Ground-state Energy Density | 41 |
| 3.3.2 | Domain Walls | 41 |
| 3.3.3 | Clustering of Ground States | 42 |
| 3.3.4 | Low-energy Excitations | 42 |
| 3.3.5 | Phase Diagram | 43 |
| 3.4 | Outlook | 43 |
| | References | 44 |
| 4 | Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch-and-cut
F. Liers, M. Jünger, G. Reinelt, and G. Rinaldi | 47 |
| 4.1 | Introduction | 47 |
| 4.2 | Ground States and Maximum Cuts | 48 |
| 4.3 | A General Scheme for Solving Hard Max-cut Problems | 51 |
| 4.4 | Linear Programming Relaxations of Max-cut | 55 |
| 4.5 | Branch-and-cut | 60 |
| 4.6 | Results of Exact Ground-state Computations | 62 |
| 4.7 | Advantages of Branch-and-cut | 65 |
| 4.8 | Challenges for the Years to Come | 66 |
| | References | 68 |
| 5 | Counting States and Counting Operations
A. Alan Middleton | 71 |
| 5.1 | Introduction | 71 |
| 5.2 | Physical Questions about Ground States | 72 |
| 5.2.1 | Homogeneous Models | 72 |
| 5.2.2 | Magnets with Frozen Disorder | 73 |
| 5.3 | Finding Low-energy Configurations | 75 |
| 5.3.1 | Physically Motivated Approaches | 75 |
| 5.3.2 | Combinatorial Optimization | 76 |
| 5.3.3 | Ground-state Algorithm for the RFIM | 78 |
| 5.4 | The Energy Landscape: Degeneracy and Barriers | 80 |
| 5.5 | Counting States | 82 |
| 5.5.1 | Ground-state Configuration Degeneracy | 83 |
| 5.5.2 | Thermodynamic State | 85 |
| 5.5.3 | Numerical Studies of Zero-temperature States | 86 |
| 5.6 | Running Times for Optimization Algorithms | 91 |
| 5.6.1 | Running Times and Evolution of the Heights | 92 |
| 5.6.2 | Heuristic Derivation of Running Times | 94 |
| 5.7 | FurtherDirections | 95 |
| | References | 96 |
| 6 | Computing the Potts Free Energy and Submodular Functions
J.-C. Anglčs d'Auriac | 101 |
| 6.1 | Introduction | 101 |
| 6.2 | The Potts Model | 102 |
| 6.2.1 | Definition of the Potts Model | 102 |
| 6.2.2 | Some Results for Non-random Models | 103 |
| 6.2.3 | The Ferromagnetic Random Bond Potts Model | 103 |
| 6.2.4 | High Temperature Development | 103 |
| 6.2.5 | Limit of an Infinite Number of States | 104 |
| 6.3 | Basics on the Minimization of Submodular Functions | 105 |
| 6.3.1 | Definition of Submodular Functions | 105 |
| 6.3.2 | A simple Characterization | 105 |
| 6.3.3 | Examples | 105 |
| 6.3.4 | Minimization of Submodular Function | 106 |
| 6.4 | Free Energy of the Potts Model in the Infinite q-Limit | 107 |
| 6.4.1 | The Method | 108 |
| 6.4.2 | The Auxiliary Problem | 108 |
| 6.4.3 | The Max-flow Problem: the Goldberg and Tarjan Algorithm | 111 |
| 6.4.4 | About the Structure of the Optimal Sets | 111 |
| 6.5 | Implementation and Evaluation | 112 |
| 6.5.1 | Implementation | 112 |
| 6.5.2 | Example of Application | 114 |
| 6.5.3 | Evaluation of the CPU Time | 114 |
| 6.5.4 | Memory Requirement | 114 |
| 6.5.5 | Various Possible Improvements | 115 |
| 6.6 | Conclusion | 116 |
| | References | 117 |
| | | |
| Part II | Phase Transitions in Combinatorial Optimization Problems | 119 |
| | | |
| 7 | The Random 3-satisfiability Problem: From the Phase Transition to the Efficient Generation of Hard, but Satisfiable Problem Instances
M. Weigt | 121 |
| 7.1 | Introduction | 121 |
| 7.2 | Random 3-SAT and the SAT/UNSAT Transition | 122 |
| 7.2.1 | Numerical Results | 123 |
| 7.2.2 | Using Statistical Mechanics | 124 |
| 7.3 | Satisfiable Random 3-SAT Instances | 127 |
| 7.3.1 | The Naive Generator | 129 |
| 7.3.2 | Unbiased Generators | 130 |
| 7.4 | Conclusion | 135 |
| | References | 136 |
| 8 | Analysis of Backtracking Procedures for Random Decision Problems
S. Cocco, L. Ein-Dor, and R. Monasson | 139 |
| 8.1 | Introduction | 139 |
| 8.2 | Phase Diagram, Search Trajectories and the Easy SAT Phase | 143 |
| 8.2.1 | Overview of Concepts Useful to DPLL Analysis | 144 |
| 8.2.2 | Clause Populations: Flows, Averages and Fluctuations | 145 |
| 8.2.3 | Average-case Analysis in the Absence of Backtracking | 147 |
| 8.2.4 | Occurrence of Contradictions and Polynomial SAT Phase | 150 |
| 8.3 | Analysis of the Search Tree Growth in the UNSAT Phase | 153 |
| 8.3.1 | Numerical Experiments | 153 |
| 8.3.2 | Parallel Growth Process and Markovian Evolution Matrix | 155 |
| 8.3.3 | Generating Function and Large-sizeScaling | 158 |
| 8.3.4 | Interpretation in Terms of Growth Process | 161 |
| 8.4 | Hard SAT Phase:Average Case and Fluctuations | 164 |
| 8.4.1 | Mixed Branchand Tree Trajectories | 164 |
| 8.4.2 | Distribution of Running Times | 165 |
| 8.4.3 | Large Deviation Analysis of the First Branch in the Tree | 167 |
| 8.5 | The Random Graph Coloring Problem | 171 |
| 8.5.1 | Description of DPLL Algorithm for Coloring | 171 |
| 8.5.2 | Coloring in the Absence of Backtracking | 172 |
| 8.5.3 | Coloring in the Presence of Massive Backtracking | 173 |
| 8.6 | Conclusions | 177 |
| | References | 179 |
| 9 | New Iterative Algorithms for Hard Combinatorial Problems
R. Zecchina | 183 |
| 9.1 | Introduction | 183 |
| 9.2 | Combinatorial Decision Problems, K-SAT and the Factor Graph Representation | 185 |
| 9.2.1 | Random K-SAT | 186 |
| 9.3 | Growth Process Algorithm: Probabilities, Messages and Their Statistics | 190 |
| 9.4 | Traditional Message-passing Algorithm: Belief Propagation as Simple Cavity Equations | 192 |
| 9.5 | Survey Propagation Equations | 194 |
| 9.6 | Decimating Variables According to Their Statistical Bias | 195 |
| 9.7 | Conclusions andPerspectives | 197 |
| | References | 199 |
| | | |
| Part III | New Heuristics and Interdisciplinary Applications | 203 |
| | | |
| 10 | Hysteretic Optimization
K.F. Pál | 205 |
| 10.1 | Hysteretic Optimization for Ising Spin Glasses | 206 |
| 10.2 | Generalization to Other Optimization Problems | 214 |
| 10.3 | Application to the Traveling Salesman Problem | 221 |
| 10.4 | Outlook | 224 |
| | References | 226 |
| 11 | Extremal Optimization
S. Boettcher | 227 |
| 11.1 | Emerging Optimality | 227 |
| 11.2 | ExtremalOptimization | 228 |
| 11.2.1 | BasicNotions | 228 |
| 11.2.2 | EO Algorithm | 230 |
| 11.2.3 | Extremal Selection | 231 |
| 11.2.4 | Rank Ordering | 232 |
| 11.2.5 | Defining Fitness | 234 |
| 11.2.6 | Distinguishing EO from other Heuristics | 235 |
| 11.2.7 | Implementing EO | 236 |
| 11.3 | Numerical Results for EO | 238 |
| 11.3.1 | Early Results | 239 |
| 11.3.2 | Applications of EO by Others | 242 |
| 11.3.3 | Large-scale Simulations of Spin Glasses | 243 |
| 11.4 | Theoretical Investigations | 246 |
| | References | 249 |
| 12 | Sequence Alignments
A.K. Hartmann | 253 |
| 12.1 | Molecular Biology | 253 |
| 12.2 | Alignments and Alignment Algorithms | 259 |
| 12.3 | Low-probability Tail of Alignment Scores | 266 |
| | References | 271 |
| 13 | Protein Folding in Silico - the Quest for Better Algorithms
U.H.E. Hansmann) | 275 |
| 13.1 | Introduction | 275 |
| 13.2 | Energy Landscape Paving | 277 |
| 13.3 | Beyond Global Optimization | 280 |
| 13.3.1 | Parallel Tempering | 280 |
| 13.3.2 | Multicanonical Sampling and Other Generalized-ensemble Techniques | 283 |
| 13.4 | Results | 288 |
| 13.4.1 | Helix Formation and Folding | 288 |
| 13.4.2 | Structure Predictions of Small Proteins | 290 |
| 13.5 | Conclusion | 293 |
| | References | 293 |
| | Index | 297 |
| | | |
