Statistical mechanics methods and phase transitions in optimization problems

Recently, it has been recognized that phase transitions play an important r ole in the probabilistic analysis of combinatorial optimization problems. H owever, there are in fact many other relations that lead to close ties betw een computer science and statistical physics. This review aims at presentin g the tools and concepts designed by physicists to deal with optimization o r decision problems in a language accessible for computer scientists and ma thematicians, with no prerequisites in physics. We first introduce some ele mentary methods of statistical mechanics and then progressively cover the t ools appropriate for disordered systems. In each case, we apply these metho ds to study the phase transitions or the statistical properties of the opti mal solutions in various combinatorial problems. We cover in detail the Ran dom Graph, the Satisfiability, and the Traveling Salesman problems. Referen ces to the physics literature on optimization are provided. We also give ou r perspective regarding the interdisciplinary contribution of physics to co mputer science. (C) 2001 Elsevier Science B.V. All rights reserved.