Optimization algorithms in physics. (English) Zbl 1003.82002

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.


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