New Optimization Algorithms in Physics

Alexander Hartmann studied computer science and physics at the universities of Hagen, Duisburg and Heidelberg, Germany. After receiving his PhD in 1998, he went as a postdoc first to the University of Gottingen, Germany, then to the University of California at Santa Cruz and the Ecole Normale Superieure, France. In 2002, he returned to the University of Gottingen, where he is currently heading a junior research group. His research interests comprise computer simulations, disordered magnetic systems, surface physics, combinatorial optimization and bioinformatics. Heiko Rieger received his PhD in theoretical physics in 1989 at the Universitat zu Koln Germany. From 1990 to 1992, he worked as a postdoc at the University of Maryland at College Park and at the University of California at Santa Cruz. In 1994, he got his habilitation in theoretical physics and was a Heisenberg fellow from 1996 to 1999, working at the Forschungszentrum Julich. He started teaching as a professor for theoretical physics at the Universitat des Saarlandes (Saarbrucken, Germany) in 1999. His main research areas are: statistical physics and computational physics, in particular disordered and glassy systems, non--equilibrium dynamics, stochastic processes, complex systems, Monte Carlo simulations and combinatorial optimization.

List of Contributors. 1 Introduction (A.K. Hartmann and H. Rieger). Part I: Applications in Physics. 2 Cluster Monte Carlo Algorithms (W. Krauth). 2.1 Detailed Balance and a priori Probabilities. 2.2 The Wolff Cluster Algorithm for the Ising Model. 2.3 Cluster Algorithm for Hard Spheres and Related Systems. 2.4 Applications. 2.4.1 Phase Separation in Binary Mixtures. 2.4.2 Polydisperse Mixtures. 2.4.3 Monomer--Dimer Problem. 2.5 Limitations and Extensions. References. 3 Probing Spin Glasses with Heuristic Optimization Algorithms (O.C. Martin). 3.1 Spin Glasses. 3.1.1 Motivations. 3.1.2 The Ising Model. 3.1.3 Models of Spin Glasses. 3.1.4 Some Challenges. 3.2 Some Heuristic Algorithms. 3.2.1 General Issues. 3.2.2 Variable Depth Search. 3.2.3 Genetic Renormalization Algorithm. 3.3 A survey of Physics Results. 3.3.1 Convergence of the Ground--state Energy Density. 3.3.2 Domain Walls. 3.3.3 Clustering of Ground States. 3.3.4 Low--energy Excitations. 3.3.5 Phase Diagram. 3.4 Outlook. References. 4 Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch--and--cut (F. Liers, M. Junger, G. Reinelt, and G. Rinaldi). 4.1 Introduction. 4.2 Ground States and Maximum Cuts. 4.3 A General Scheme for Solving Hard Max--cut Problems. 4.4 Linear Programming Relaxations of Max--cut. 4.5 Branch--and--cut. 4.6 Results of Exact Ground--state Computations. 4.7 Advantages of Branch--and--cut. 4.8 Challenges for the Years to Come. References. 5 Counting States and Counting Operations (A. Alan Middleton). 5.1 Introduction. 5.2 Physical Questions about Ground States. 5.2.1 Homogeneous Models. 5.2.2 Magnets with Frozen Disorder. 5.3 Finding Low--energy Configurations. 5.3.1 Physically Motivated Approaches. 5.3.2 Combinatorial Optimization. 5.3.3 Ground--state Algorithm for the RFIM. 5.4 The Energy Landscape: Degeneracy and Barriers. 5.5 Counting States. 5.5.1 Ground--state Configuration Degeneracy. 5.5.2 Thermodynamic State. 5.5.3 Numerical Studies of Zero--temperature States. 5.6 Running Times for Optimization Algorithms. 5.6.1 Running Times and Evolution of the Heights. 5.6.2 Heuristic Derivation of Running Times. 5.7 Further Directions. References. 6 Computing the Potts Free Energy and Submodular Functions (J.--C. Angles d'Auriac). 6.1 Introduction. 6.2 The Potts Model. 6.2.1 Definition of the Potts Model. 6.2.2 Some Results for Non--random Models. 6.2.3 The Ferromagnetic Random Bond Potts Model. 6.2.4 High Temperature Development. 6.2.5 Limit of an Infinite Number of States. 6.3 Basics on the Minimization of Submodular Functions. 6.3.1 Definition of Submodular Functions. 6.3.2 A simple Characterization. 6.3.3 Examples. 6.3.4 Minimization of Submodular Function. 6.4 Free Energy of the Potts Model in the Infinite q--Limit. 6.4.1 The Method. 6.4.2 The Auxiliary Problem. 6.4.3 The Max--flow Problem: the Goldberg and Tarjan Algorithm. 6.4.4 About the Structure of the Optimal Sets. 6.5 Implementation and Evaluation. 6.5.1 Implementation. 6.5.2 Example of Application. 6.5.3 Evaluation of the CPU Time. 6.5.4 Memory Requirement. 6.5.5 Various Possible Improvements. 6.6 Conclusion. References. Part II Phase Transitions in Combinatorial Optimization Problems. 7 The Random 3--satisfiability Problem: From the Phase Transition to the Efficient Generation of Hard, but Satisfiable Problem Instances (M. Weigt). 7.1 Introduction. 7.2 Random 3--SAT and the SAT/UNSAT Transition. 7.2.1 Numerical Results. 7.2.2 Using Statistical Mechanics. 7.3 Satisfiable Random 3--SAT Instances. 7.3.1 The Naive Generator. 7.3.2 Unbiased Generators. 7.4 Conclusion. References. 8 Analysis of Backtracking Procedures for Random Decision Problems (S. Cocco, L. Ein--Dor, and R. Monasson). 8.1 Introduction. 8.2 Phase Diagram, Search Trajectories and the Easy SAT Phase. 8.2.1 Overview of Concepts Useful to DPLL Analysis. 8.2.2 Clause Populations: Flows, Averages and Fluctuations. 8.2.3 Average--case Analysis in the Absence of Backtracking. 8.2.4 Occurrence of Contradictions and Polynomial SAT Phase. 8.3 Analysis of the Search Tree Growth in the UNSAT Phase. 8.3.1 Numerical Experiments. 8.3.2 Parallel Growth Process and Markovian Evolution Matrix. 8.3.3 Generating Function and Large--size Scaling. 8.3.4 Interpretation in Terms of Growth Process. 8.4 Hard SAT Phase: Average Case and Fluctuations. 8.4.1 Mixed Branch and Tree Trajectories. 8.4.2 Distribution of Running Times. 8.4.3 Large Deviation Analysis of the First Branch in the Tree. 8.5 The Random Graph Coloring Problem. 8.5.1 Description of DPLL Algorithm for Coloring. 8.5.2 Coloring in the Absence of Backtracking. 8.5.3 Coloring in the Presence of Massive Backtracking. 8.6 Conclusions. References. 9 New Iterative Algorithms for Hard Combinatorial Problems (R. Zecchina). 9.1 Introduction. 9.2 Combinatorial Decision Problems, K--SAT and the Factor Graph Representation. 9.2.1 Random K--SAT. 9.3 Growth Process Algorithm: Probabilities, Messages and Their Statistics. 9.4 Traditional Message--passing Algorithm: Belief Propagation as Simple Cavity Equations. 9.5 Survey Propagation Equations. 9.6 Decimating Variables According to Their Statistical Bias. 9.7 Conclusions and Perspectives. References. Part III New Heuristics and Interdisciplinary Applications. 10 Hysteretic Optimization ((K.F. Pal). 10.1 Hysteretic Optimization for Ising Spin Glasses. 10.2 Generalization to Other Optimization Problems. 10.3 Application to the Traveling Salesman Problem. 10.4 Outlook. References. 11 Extremal Optimization (S. Boettcher) 227 11.1 Emerging Optimality. 11.2 Extremal Optimization. 11.2.1 Basic Notions. 11.2.2 EO Algorithm. 11.2.3 Extremal Selection. 11.2.4 Rank Ordering. 11.2.5 Defining Fitness. 11.2.6 Distinguishing EO from other Heuristics. 11.2.7 Implementing EO. 11.3 Numerical Results for EO. 11.3.1 Early Results. 11.3.2 Applications of EO by Others. 11.3.3 Large--scale Simulations of Spin Glasses. 11.4 Theoretical Investigations. References. 12 Sequence Alignments (A.K. Hartmann) 253 12.1 Molecular Biology. 12.2 Alignments and Alignment Algorithms. 12.3 Low--probability Tail of Alignment Scores. References. 13 Protein Folding in Silico -- the Quest for Better Algorithms (U.H.E. Hansmann). 13.1 Introduction. 13.2 Energy Landscape Paving. 13.3 Beyond Global Optimization. 13.3.1 Parallel Tempering. 13.3.2 Multicanonical Sampling and Other Generalized--ensemble Techniques. 13.4 Results. 13.4.1 Helix Formation and Folding. 13.4.2 Structure Predictions of Small Proteins. 13.5 Conclusion. References. Index.