Confidence Limits for Global Optima Based on Heuristic Solutions to Difficult Optimization Problems: A Simulation Study

SYNOPTIC ABSTRACT

For many optimization problems approximate solutions based on heuristic algorithms are the only practical solutions available. Heuristic algorithms often utilize random sampling to select a starting point or to investigate possible completions of a partial solution, etc. When such an algorithm has been independently executed several times, one wonders: “How close is the best observed value of the objective function to the global optimum?” A statistical answer to this question is a confidence limit, such that with user-specified confidence the global optimum is between the best observed objective function value and the confidence limit. Three approaches to the generation of such confidence limits are identified, and their empirical behavior in a Monte Carlo study reported.

Key Words and Phrases:

• heuristic algorithms
• random sampling
• limiting distributions of order statistics
• goodness-of-fit statistics
• Monte Carlo