## Description

Optimization problems occur very frequently in physics. Some of them are easy to handle with conventional methods also used in other areas such as economy or operations research. But as soon as a huge number of degrees of freedom are involved, as is typically the case in statistical physics, condensed matter, astrophysics and biophysics, conventional methods fail to find the optimum in a reasonable time and new methods have to be invented. This book contains a representative collection of new optimization algorithms that have been devised by physicists from various fields, sometimes based on methods developed by computer scientists and mathematicians. However, it is not a mere collection of algorithms but tries to demonstrates their scope and efficiency by describing typical situations in physics where they are useful.

The individual articles of this collections are self-contained and should be understandable for scientists routinely using numerical tools. A more basic and pedagogical introduction into optimization algorithms is our book on Optimization Algorithms in Physics, which can serve as an appendix for the newcomer to this field of computational physics or for undergraduate students. The reason why we found it necessary to compose another book in this field with a greater focus is the fact that the application of optimization methods is one of the strongest growing fields in physics. The main reasons for these current developments are the following key factors:

First of all great progress has been made in the development of new combinatorial optimization methods in computer science. Using these sophisticated approaches, much larger system sizes of the corresponding physical systems can be treated. For many models the systems sizes which were accessible before, were too small to obtain reliable and significant data. However, this is now possible. In this way computer science has helped physics.

But knowledge transfer also works the other way round. Physics provides still new insights and methods of treating optimization problems, such as the earlier invention of the simulated annealing technique. Recent algorithmic developments in physics are, e.g., the extremal optimization method or the hysteric optimization approach, both covered in this book.

Moreover, phase transitions were recently found in “classical” optimization problems within theoretical computer science, during the study of suitably parameterized ensembles. These phase transitions very often coincide with peaks of the running time or with changes of the typical-case complexity from polynomial to exponential. As well as the gain from taking the physical viewpoint, by mapping the optimization problems to physical systems and applying methods from statistical physics, it is possible to obtain many results, which have not been found with traditional mathematical techniques. This is true also for the analysis of the typical-case complexity of (random) algorithms.