A review of the Statistical Mechanics approach to Random Optimization Problems <s> I. INTRODUCTION <s> This clearly written , mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NPcomplete problems, more. All chapters are supplemented by thoughtprovoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering. Mathematicians wishing a self-contained introduction need look no further.—American Mathematical Monthly. 1982 ed. <s> BIB001 </s> A review of the Statistical Mechanics approach to Random Optimization Problems <s> I. INTRODUCTION <s> This book contains a detailed and self-contained presentation of the replica theory of infinite range spin glasses. The authors also explain recent theoretical developments, paying particular attention to new applications in the study of optimization theory and neural networks. About two-thirds of the book are a collection of the most interesting and pedagogical articles on the subject. <s> BIB002
The connection between the statistical physics of disordered systems and optimization problems in computer science dates back from twenty years at least BIB002 . In combinatorial optimization one is given a cost function (the length of a tour in the traveling salesman problem (TSP), the number of violated constraints in constraint satisfaction problems, . . . ) over a set of variables and looks for the minimal cost over an allowed range for those variables. Finding the true minimum may be complicated, and requires bigger and bigger computational efforts as the number of variables to be minimized over increases BIB001 . Statistical physics is at first sight very different. The scope is to deduce the macroscopic, that is, global properties of a physical system, for instance a gas, a liquid or a solid, from the knowledge of the energetic interactions of its elementary components (molecules, atoms or ions). However, at very low temperature, these elementary components are essentially forced to occupy the spatial conformation minimizing the global energy of the system. Hence low temperature statistical physics can be seen as the search for minimizing a cost function whose expression reflects the laws of Nature or, more humbly, the degree of accuracy retained in its description. This problem is generally not difficult to solve for non disordered systems where the lowest energy conformation are crystals in which components are regularly spaced from each other. Yet the presence of disorder, e.g. impurities, makes the problem very difficult and finding the conformation with minimal energy is a true optimization problem. At the beginning of the eighties, following the works of G. Parisi and others on systems called spin glasses BIB002 , important progresses were made in the statistical physics of disordered systems. Those progresses made possible the quantitative study of the properties of systems given some distribution of the disorder (for instance the location of impurities) such as the average minimal energy and its fluctuations. The application to optimization problems was natural and led to beautiful studies on (among others) the average properties of the minimal tour length in the TSP, the minimal cost in Bipartite Matching, for some specific instance distributions BIB002 . Unfortunately statistical physicists and computer scientists did not establish close ties on a large scale at that time. The reason could have been of methodological nature [3] . While physicists were making statistical statements, true for a given distribution of inputs, computer scientists were rather interested in solving one (or several) particular instances of a problem. The focus was thus on efficient ways to do so, that is, requiring a computational effort growing not too quickly with the number of data defining the instance. Knowing precisely the typical properties for a given, academic distribution of instances did not help much to solve practical cases. At the beginning of the nineties practitionners in artificial intelligence realized that classes of random constraint satisfaction problems used as artificial benchmarks for search algorithms exhibited abrupt changes of behaviour when some control parameter were finely tuned  . The most celebrated example was random k-Satisfiability, where one looks for a solution to a set of random logical constraints over a set of Boolean variables. It appeared that, for large sets of variables, there was a critical value of the number of constraints per variable below which there almost surely existed solutions, and above which solutions were absent. An important feature was that the performances of known search algorithms drastically worsened in the vicinity of this critical ratio. In addition to its intrinsic mathematical interest the random k-SAT problem was therefore worth to be studied for 'practical' reasons. This critical phenomenon, strongly reminiscent of phase transitions in condensed matter physics, led to a revival of the research at the interface between statistical physics and computer science, which is still very active. The purpose of the present review is to introduce the non physicist reader to some concepts required to understand the literature in the field and to present some major results. We shall in particular discuss the refined picture of the satisfiable phase put forward in statistical mechanics studies and the algorithmic approach (Survey Propagation, an extension of Belief Propagation used in communication theory and statistical inference) this picture suggested. While the presentation will mostly focus on the k-Satisfiability problem (with random constraints) we will occasionally discuss another computational problem, namely, linear systems of Boolean equations. A good reason to do so is that this problem exhibits some essential features encountered in random k-Satisfiability, while being technically simpler to study. In addition it is closely related to error-correcting codes in communication theory. The chapter is divided into four main parts. In Section II we present the basic statistical physics concepts necessary to understand the onset of phase transitions, and to characterize the nature of the phases. Those are illustrated on a simple example of decision problem, the so-called perceptron problem. In Section III we review the scenario of the various phase transitions taking place in random k-SAT. Section IV and V present the techniques used to study various type of algorithms in optimization (local search, backtracking procedures, message passing algorithms). We end up with some conclusive remarks in Sec. VI.