Note: Intro -- New Optimization Algorithms in Physics -- Contents -- List of Contributors -- 1 Introduction -- Part I Applications in Physics -- 2 Cluster Monte Carlo Algorithms -- 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 -- 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 -- 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 -- 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 -- 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 -- 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 -- 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 -- 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 -- 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 -- 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 -- 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 -- 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.