Point estimation of a global optimum for large combinatorial problems

The basis for this paper is in the following observation: for a given “ intractable” optimization problem for which no efficient solution technique exists, if we can devise a systematic procedure for generating independent, heuristic solutions, we should be able to apply statistical extreme-value theory in order to obtain point estimates for the globally optimal solution. This observation has been mechanized in order to evaluate heuristic solutions and assess deviations from optimality, the strategy developed is applicable to a host of combinatorial problems. The assumptions of our model, along with computational experience are discussed.