Statistical indicators of optimality

Neighborhood search has been used with some success in providing approximate solutions to discrete optimization problems. The technique produces solutions which may be locally but not globally optimal. For a particular class of problems this paper describes a method for analyzing the relative effectiveness associated with different neighborhoods in terms of the probability that a local optimum is in fact global. The analysis is then applied to the 5-city Travelling Salesman Problem for which two neighborhoods of like size are compared. It is found that local optimality with respect to one of these neighborhoods is roughly twice as likely to indicate global optimality as is local optimality with respect to the other. It is felt that further development of the techniques described in this paper might lead to computer designed heuristics for certain discrete optimization problems.