NEW OPTIMIZATION ALGORITHMS IN PHYSICS

By SOPHIA ROBINSON

CONTENTS INTRODUCTION PART I APPLICATIONS IN PHYSICS CLUSTER MONTE CARLO ALGORITHMS DETAILED BALANCE AND A PRIORI PROBABILITIES THE WOLFF CLUSTER ALGORITHM FOR THE ISING MODEL CLUSTER ALGORITHM FOR HARD SPHERES AND RELATED SYSTEMS APPLICATIONS PHASE SEPARATION IN BINARY MIXTURES POLYDISPERSE MIXTURES MONOMER-DIMER PROBLEM LIMITATIONS AND EXTENSIONS REFERENCES PROBING SPIN GLASSES WITH HEURISTIC OPTIMIZATION ALGORITHMS SPIN GLASSES MOTIVATIONS THE ISING MODEL MODELS OF SPIN GLASSES SOME CHALLENGES SOME HEURISTIC ALGORITHMS GENERAL ISSUES VARIABLE DEPTH SEARCH GENETIC RENORMALIZATION ALGORITHM A SURVEY OF PHYSICS RESULTS CONVERGENCE OF THE GROUND-STATE ENERGY DENSITY DOMAIN WALLS CLUSTERING OF GROUND STATES LOW-ENERGY EXCITATIONS PHASE DIAGRAM OUTLOOK COMPUTING EXACT GROUND STATES OF HARD ISING SPIN GLASS PROBLEMS BY BRANCH-AND-CUT GROUND STATES AND MAXIMUM CUTS A GENERAL SCHEME FOR SOLVING HARD MAX-CUT PROBLEMS LINEAR PROGRAMMING RELAXATIONS OF MAX-CUT BRANCH-AND-CUT RESULTS OF EXACT GROUND-STATE COMPUTATIONS ADVANTAGES OF BRANCH-AND-CUT CHALLENGES FOR THE YEARS TO COME COUNTING STATES AND COUNTING OPERATIONS PHYSICAL QUESTIONS ABOUT GROUND STATES HOMOGENEOUS MODELS MAGNETS WITH FROZEN DISORDER FINDING LOW-ENERGY CON?GURATIONS PHYSICALLY MOTIVATED APPROACHES COMBINATORIAL OPTIMIZATION GROUND-STATE ALGORITHM FOR THE RFIM THE ENERGY LANDSCAPE: DEGENERACY AND BARRIERS COUNTING STATES GROUND-STATE CON?GURATION DEGENERACY THERMODYNAMIC STATE NUMERICAL STUDIES OF ZERO-TEMPERATURE STATES RUNNING TIMES FOR OPTIMIZATION ALGORITHMS RUNNING TIMES AND EVOLUTION OF THE HEIGHTS HEURISTIC DERIVATION OF RUNNING TIMES FURTHER DIRECTIONS COMPUTING THE POTTS FREE ENERGY AND SUBMODULAR FUNCTIONS THE POTTS MODEL DE?NITION OF THE POTTS MODEL SOME RESULTS FOR NON-RANDOM MODELS THE FERROMAGNETIC RANDOM BOND POTTS MODEL HIGH TEMPERATURE DEVELOPMENT LIMIT OF AN IN?NITE NUMBER OF STATES BASICS ON THE MINIMIZATION OF SUBMODULAR FUNCTIONS DE?NITION OF SUBMODULAR FUNCTIONS A SIMPLE CHARACTERIZATION EXAMPLES MINIMIZATION OF SUBMODULAR FUNCTION FREE ENERGY OF THE POTTS MODEL IN THE IN?NITE Q-LIMIT THE METHOD THE AUXILIARY PROBLEM THE MAX-?OW PROBLEM: THE GOLDBERG AND TARJAN ALGORITHM ABOUT THE STRUCTURE OF THE OPTIMAL SETS IMPLEMENTATION AND EVALUATION IMPLEMENTATION EXAMPLE OF APPLICATION EVALUATION OF THE CPU TIME MEMORY REQUIREMENT VARIOUS POSSIBLE IMPROVEMENTS CONCLUSION PART II PHASE TRANSITIONS IN COMBINATORIAL OPTIMIZATION PROBLEMS THE RANDOM 3-SATIS?ABILITY PROBLEM: FROM THE PHASE TRANSITION TO THE EF?CIENT GENERATION OF HARD, BUT SATIS?ABLE PROBLEM INSTANCES RANDOM 3-SAT AND THE SAT/UNSAT TRANSITION NUMERICAL RESULTS USING STATISTICAL MECHANICS SATIS?ABLE RANDOM 3-SAT INSTANCES THE NAIVE GENERATOR UNBIASED GENERATORS ANALYSIS OF BACKTRACKING PROCEDURES FOR RANDOM DECISION PROBLEMS PHASE DIAGRAM, SEARCH TRAJECTORIES AND THE EASY SAT PHASE OVERVIEW OF CONCEPTS USEFUL TO DPLL ANALYSIS CLAUSE POPULATIONS: FLOWS, AVERAGES AND FLUCTUATIONS AVERAGE-CASE ANALYSIS IN THE ABSENCE OF BACKTRACKING OCCURRENCE OF CONTRADICTIONS AND POLYNOMIAL SAT PHASE ANALYSIS OF THE SEARCH TREE GROWTH IN THE UNSAT PHASE NUMERICAL EXPERIMENTS PARALLEL GROWTH PROCESS AND MARKOVIAN EVOLUTION MATRIX GENERATING FUNCTION AND LARGE-SIZE SCALING INTERPRETATION IN TERMS OF GROWTH PROCESS HARD SAT PHASE: AVERAGE CASE AND FLUCTUATIONS MIXED BRANCH AND TREE TRAJECTORIES DISTRIBUTION OF RUNNING TIMES LARGE DEVIATION ANALYSIS OF THE FIRST BRANCH IN THE TREE THE RANDOM GRAPH COLORING PROBLEM DESCRIPTION OF DPLL ALGORITHM FOR COLORING COLORING IN THE ABSENCE OF BACKTRACKING COLORING IN THE PRESENCE OF MASSIVE BACKTRACKING CONCLUSIONS NEW ITERATIVE ALGORITHMS FOR HARD COMBINATORIAL PROBLEMS RANDOM K-SAT GROWTH PROCESS ALGORITHM: PROBABILITIES, MESSAGES AND THEIR STATISTICS TRADITIONAL MESSAGE-PASSING ALGORITHM: BELIEF PROPAGATION AS SIMPLE CAVITY EQUATIONS SURVEY PROPAGATION EQUATIONS DECIMATING VARIABLES ACCORDING TO THEIR STATISTICAL BIAS CONCLUSIONS AND PERSPECTIVES PART III NEW HEURISTICS AND INTERDISCIPLINARY APPLICATIONS 10 HYSTERETIC OPTIMIZATION 101 HYSTERETIC OPTIMIZATION FOR ISING SPIN GLASSES 102 GENERALIZATION TO OTHER OPTIMIZATION PROBLEMS 103 APPLICATION TO THE TRAVELING SALESMAN PROBLEM 104 OUTLOOK 11 EXTREMAL OPTIMIZATION 111 EMERGING OPTIMALITY 112 EXTREMAL OPTIMIZATION 1121 BASIC NOTIONS 1122 EO ALGORITHM 1123 EXTREMAL SELECTION 1124 RANK ORDERING 1125 DE?NING FITNESS 1126 DISTINGUISHING EO FROM OTHER HEURISTICS 1127 IMPLEMENTING EO 113 NUMERICAL RESULTS FOR EO 1131 EARLY RESULTS 1132 APPLICATIONS OF EO BY OTHERS 1133 LARGE-SCALE SIMULATIONS OF SPIN GLASSES 114 THEORETICAL INVESTIGATIONS 12 SEQUENCE ALIGNMENTS 121 MOLECULAR BIOLOGY 122 ALIGNMENTS AND ALIGNMENT ALGORITHMS 123 LOW-PROBABILITY TAIL OF ALIGNMENT SCORES 13 PROTEIN FOLDING IN SILICO – THE QUEST FOR BETTER ALGORITHMS 131 INTRODUCTION 132 ENERGY LANDSCAPE PAVING 133 BEYOND GLOBAL OPTIMIZATION 1331 PARALLEL TEMPERING 1332 MULTICANONICAL SAMPLING AND OTHER GENERALIZED-ENSEMBLE TECHNIQUES 134 RESULTS 1341 HELIX FORMATION AND FOLDING 1342 STRUCTURE PREDICTIONS OF SMALL PROTEINS 135 CONCLUSION