Optimization algorithms in physics. (English) Zbl 1003.82002

Hartmann, Alexander K.; Rieger, Heiko

Berlin: Wiley-VCH. x, 372 p. (2002).

The main aim of the book - as declared in its preface - is to supply physicists with the basic knowledge in combinatorial and stochastic optimization and, at the same time, to describe, for computer scientists, the physical models and problems to which optimization algorithms may be successfully applied. The book consists of thirteen chapters written in a very clear and understandable manner, supplied with numerous examples, illustrations and a detailed bibliography.
The first four chapters are addressed mainly to physicists. In the first chapter the authors give a brief introduction to optimization, which is based on physical examples like spin glasses. The second chapter is dedicated to complexity theory - a very rapidly developing interdisciplinary branch of science (for more information on this topic, I would suggest to visit the website http://www.physik.uni-bielefeld.de/complexity/). Basic information on graphs and graph algorithms is provided in chapters 3 and 4.
The fifth chapter is addressed mainly to computer scientists. It describes the main notions and popular models of statistical physics, including phase transitions, finite-size scaling, disordered systems. Maximum-flow methods are described in chapter 6, where they are applied to the problem of calculating ground states of the random-field Ising model and of the diluted antiferromagnets in a field. In chapter 7 the ground state configuration problem for directed polymers in a random environment is studied by means of minimum-cost flows. Here general minimum-cost flow algorithms are also described and illustrated. Genetic algorithms are presented in chapter 8. Along with the general description of these algorithms the authors present their application to the calculation of the ground state wave function of one-dimensional quantum systems and to retrieving hidden parameters of colliding galaxies from the two-dimensional images obtained by telescopes. Chapter 9 is dedicated to the problem of calculating ground states of spin glasses. In chapter 10 two-dimensional spin glass models are used to introduce matching problems, which is followed by the detailed description of matching algorithms. The chapter is concluded by overviewing some results for spin glasses.
Stochastic optimization methods are described in chapter 11. Branch-and-bound methods are described in chapter 12. Chapter 13 is dedicated to practical issues, where typical problems of conducting research via computer simulations are discussed.
Summing up, the book might be very helpful for a vast variety of scientists, including those who apply ideas and methods of statistical physics in economy, sociology, biology.

Reviewer: Yuri Kozitsky (Lublin)

MSC:

82-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to statistical mechanics
00A79	Physics
90C90	Applications of mathematical programming
82-08	Computational methods (statistical mechanics) (MSC2010)
90C27	Combinatorial optimization
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C15	Stochastic programming
82B80	Numerical methods in equilibrium statistical mechanics (MSC2010)
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

complexity; graph algorithms; ground state; spin glass; genetic algorithms; matching; Monte Carlo methods; branch-and-bound methods

Software:

NAG