Parameter Sensitivity of the Elastic Net Approach to the Traveling Salesman Problem

Durbin and Willshaw's elastic net algorithm can find good solutions to the TSP. The purpose of this paper is to point out that for certain ranges of parameter values, the algorithm converges into local minima that do not correspond to valid tours. The key parameter is the ratio governing the relative strengths of the two competing terms in the elastic net energy function. Based on recent work by Durbin, Szeliski and Yuille, the parameter regime in which the net may visit some cities twice is examined. Further analysis predicts the regime in which the net may fail to visit some cities at all. Understanding these limitations allows one to select the parameter value most likely to avoid either type of problem. Simulation data support the theoretical work.