# Optimization Algorithms in Physics

# Optimization Algorithms in Physics

ISBN: 978-3-527-60087-8

May 2003

320 pages

## Description

The past few years have witnessed a substantial growth in the number of applications for optimization algorithms in solving problems in the field of physics. Examples include determining the structure of molecules, estimating the parameters of interacting galaxies, the ground states of electronic quantum systems, the behavior of disordered magnetic materials, and phase transitions in combinatorial optimization problems.This book serves as an introduction to the field, while also presenting a complete overview of modern algorithms. The authors begin with the relevant foundations from computer science, graph theory and statistical physics, before moving on to thoroughly explain algorithms - backed by illustrative examples. They include pertinent mathematical transformations, which in turn are used to make the physical problems tractable with methods from combinatorial optimization. Throughout, a number of interesting results are shown for all physical examples. The final chapter provides numerous practical hints on software development, testing programs, and evaluating the results of computer experiments.

Introduction to Optimization

Complexity Theory

Graphs

Simple Graph Algorithms

Introduction to Statistical Physics

Maximum-Flow Methods

Minimum-Cost Flow Problems

Genetic Algorithms

Monte-Carlo Methods

Approximation Methods for Spin Glasses

Matching Algorithms

Branch-and-Bound Methods

Practical Issues

Complexity Theory

Graphs

Simple Graph Algorithms

Introduction to Statistical Physics

Maximum-Flow Methods

Minimum-Cost Flow Problems

Genetic Algorithms

Monte-Carlo Methods

Approximation Methods for Spin Glasses

Matching Algorithms

Branch-and-Bound Methods

Practical Issues

Book review for ChemPhysChem

"Optimization Algorithms in Physics"

By A.K. Hartmann and H. Rieger

Quenched disorder, such as impurities or lattice defects, can have major effects on the physical properties of materials. By "quenched" one means that the disorder variables are frozen-in on the timescale of the experiments and thus do not anneal away. The last 10 years have seen great progress in our understanding of such disordered systems. This has been possible in part through the introduction of new computational tools for finding ground states when the degrees of freedom are discrete, Hartmann and Rieger being two of the main actors of this thrust. Their book gives a broad perspective of the associated optimisation algorithms and also of the underlying physics issues. It will serve both as a guide and as a reference manual for graduate students and more advanced researchers wanting to work in this field. Beyond that audience, the book should also appeal to researchers interested in Thomson's problem, sphere packings, LJ atomic clusters or other continuous optimisation problems. Indeed, the book at large brings out the important physics issues that can be studied by examining ground states and also it covers some heuristic optimisation methods; both of these themes go far beyond discrete optimisation.

The book begins by introductory review chapters of complexity theory, standard graph algorithms, and statistical physics; these make the book self-contained and accessible to most readers. The rest of the book is roughly divided into three parts. First, there are those model systems whose complexity is not too high, i.e., for which the ground state can be found via a polynomial-time algorithm. Many of these very efficient algorithms are associated with shortest paths on graphs or maximum flows in networks. Model systems that fall into this class are: domain walls in disordered ferromagnets, the random field Ising model, disordered antiferromagnets in a field (DAFF), and vortex lattice problems.

Second, there are also the more difficult problems for which one probably will never have such efficient methods. In such systems, one either uses branch-and-bound type algorithms or resorts to heuristics which are not guaranteed to find the true optimum. The authors illustrate these methods on spin glasses (still a highly controversial subject) and the vertex cover problem (a computer science problem that is analogous to some extent to a discrete version of sphere packing).

In each of these chapters, the authors explain the state of the art algorithms, first using high level descriptions and then giving some pseudo-code; they also give the central physical issues and provide extensive bibliographical listings. All this makes clear the opportunities still open and what tools are likely to make further progress possible.

Finally, there is a third part to the book in case you didn't get your PhD in computational physics in the last five years. Indeed, a 60 page chapter brings you up to date on the good ways to manage a computational project, with everything from programming tools and libraries to data analysis and article preparation.

Let me stress that this book is conceived to be practical: there is an extensive index; no unnecessary formalism nor abstractions are used; each chapter goes quickly to the essential issues and to the state of the art computational methods.

Another point is that the book is self-contained except for the fact that no source code is included; note however that quite good optimisation codes are freely available on the Web and so the motivated reader should be able to get started quite quickly. Lastly, this book focuses on a still evolving research field and so it cannot give a definitive coverage; nevertheless, it should be useful for beginners and practitioners alike.

"...accessible to both physicists and computer scientists, this work explains the theoretical models and practical situations in physics which optimization problems occur..." SciTech Book News

"Optimization Algorithms in Physics"

By A.K. Hartmann and H. Rieger

Quenched disorder, such as impurities or lattice defects, can have major effects on the physical properties of materials. By "quenched" one means that the disorder variables are frozen-in on the timescale of the experiments and thus do not anneal away. The last 10 years have seen great progress in our understanding of such disordered systems. This has been possible in part through the introduction of new computational tools for finding ground states when the degrees of freedom are discrete, Hartmann and Rieger being two of the main actors of this thrust. Their book gives a broad perspective of the associated optimisation algorithms and also of the underlying physics issues. It will serve both as a guide and as a reference manual for graduate students and more advanced researchers wanting to work in this field. Beyond that audience, the book should also appeal to researchers interested in Thomson's problem, sphere packings, LJ atomic clusters or other continuous optimisation problems. Indeed, the book at large brings out the important physics issues that can be studied by examining ground states and also it covers some heuristic optimisation methods; both of these themes go far beyond discrete optimisation.

The book begins by introductory review chapters of complexity theory, standard graph algorithms, and statistical physics; these make the book self-contained and accessible to most readers. The rest of the book is roughly divided into three parts. First, there are those model systems whose complexity is not too high, i.e., for which the ground state can be found via a polynomial-time algorithm. Many of these very efficient algorithms are associated with shortest paths on graphs or maximum flows in networks. Model systems that fall into this class are: domain walls in disordered ferromagnets, the random field Ising model, disordered antiferromagnets in a field (DAFF), and vortex lattice problems.

Second, there are also the more difficult problems for which one probably will never have such efficient methods. In such systems, one either uses branch-and-bound type algorithms or resorts to heuristics which are not guaranteed to find the true optimum. The authors illustrate these methods on spin glasses (still a highly controversial subject) and the vertex cover problem (a computer science problem that is analogous to some extent to a discrete version of sphere packing).

In each of these chapters, the authors explain the state of the art algorithms, first using high level descriptions and then giving some pseudo-code; they also give the central physical issues and provide extensive bibliographical listings. All this makes clear the opportunities still open and what tools are likely to make further progress possible.

Finally, there is a third part to the book in case you didn't get your PhD in computational physics in the last five years. Indeed, a 60 page chapter brings you up to date on the good ways to manage a computational project, with everything from programming tools and libraries to data analysis and article preparation.

Let me stress that this book is conceived to be practical: there is an extensive index; no unnecessary formalism nor abstractions are used; each chapter goes quickly to the essential issues and to the state of the art computational methods.

Another point is that the book is self-contained except for the fact that no source code is included; note however that quite good optimisation codes are freely available on the Web and so the motivated reader should be able to get started quite quickly. Lastly, this book focuses on a still evolving research field and so it cannot give a definitive coverage; nevertheless, it should be useful for beginners and practitioners alike.

"...accessible to both physicists and computer scientists, this work explains the theoretical models and practical situations in physics which optimization problems occur..." SciTech Book News