This paper is concerned with large combinatorial problems for which no exact and efficient optimization technique exists. In order to estimate the exact optimum, we combine a hill-climbing procedure with a random generation of initial solutions, thereby inducing a distribution of local optima, and after deletion of the repetitions among the observations, we follow other authors by fitting a Weibull function to that distribution. The assumptions of this statistical approach are discussed and a new confidence interval is defined. Next it is proposed to use as one unique sample space the sets of local optima associated with several heuristics. The utilization, as sample points, of the extrema from samples of local optima is also proposed. In order to determine when to stop sampling local optima, we develop an iterative stopping rule based on the statistical information provided by the estimated Weibull distributions.

Numerical results are reported for the quadratic assignment problem and for the optimal network problem. They consolidate the validity of this statistical approach. We also argue that, both from a theoretical and a practical point of view, the approach is best supported by heuristics of intermediate power.