Cavity methods in optimization problems : exact and approximated algorithms

Several optimization problems can be stated as disordered systems problems. This fact encouraged a fruitful exchange of knowledge and technical tools from one field to the other. The physical insight made possible to design new algorithms based on some physical ideas.The first part of this thesis is devoted to an introduction to the physics of disordered systems and cavity methods, with a specific attention to its relation with combinatorial optimization.The second part of the thesis is devoted to the description of some new results. In chapter 6 we give a general method to find bounds for the cost of the optimal configuration of an optimization problem. We apply it to the ground state of Ising Spin Glasses on Random Graphs.In chapter 7 we analyze the behaviour of an algorithm based on the passing of messages (Belief Propagation) on the Assignment Problem. This algorithm surprisingly results to be exact for the Assignment problem. We give a proof of the exactness of this algorithm and describe its behaviour.In chapter 8 we discuss some variants of the Assignment problem and introduce then a variant: the one-in-two problem, suggested us as a simpler but no easier version of the Traveling Salesman Problem