Finding the exact solution to a number of fundamental optimization problems (such as Bin Packing, Travelling Salesperson Problem, Vehicle Routing Problems) is very likely to be intractable. One method of gaining an understanding of these problems is to study them as stochastic models. It is then possible to estimate the average behavior of the optimal solution and develop procedures that will produce solutions that, on average, are close to the optimal. The past research of the investigator has demonstrated the relevance and the power of various methods of this approach. The main objective of this research is to make further methodological progress in the understanding of these stochastic models. In an overwhelming number of practical situations, one is faced with the problem of choosing, among a usually astronomical number of possible configurations, the one with the lowest cost (=optimal). Even in very simple cases, this is intractable. Since these problems must nonetheless be dealt with, getting a deeper understanding of them is a goal of considerable importance. One way to gain insight is to study these problems under random input. Past research has demonstrated the relevance to that study of sophisticated tools from various branches of mathematics. The main objective of the present proposal is to make further methodological progress through the study of a number of concrete questions that crystalize the limits of today's techniques.
