A new adaptive multi-start technique for combinatorial global optimizations

The authors analyze relationships among local minima for the traveling salesman and graph bisection problems under standard neighborhood structures. The present work reveals surprising correlations that suggest a globally convex, or ‘big valley’ structure in these optimization cost surfaces. In conjunction with combinatorial results that sharpen previous analyses, the analysis directly motivates a new adaptive multi-start paradigm for heuristic global optimization, wherein starting points for greedy descent are adaptively derived from the best previously found local minima. The authors test a simple instance of this method for the traveling salesman problem and obtain very significant speedups over previous multi-start implementations.