Solving large-scale optimization problems by divide-and-conquer neural networks

The authors present a neural network algorithm that is based on a divide-and-conquer strategy for solving large-scale traveling-salesman problems (TSPs). This ad hoc cut-and-splice algorithm utilizes a two-layer network with a partitioned first layer and a combining second layer. The cities of a large-scale TSP are first divided into clusters or local sets. Each local city set is represented by a neural network in the first layer, which upon convergence yields the local minimum tour. The second layer optimizes the interconnections between the local sets, forming a global final tour. The regional global (or local) minima of each cluster can be combined to form the global minima of the overall energy functions. Results of the cut-and-splice algorithm are compared with those of the single-layer modified Hopefield-Tank neural network algorithm. The invariant property is confirmed in the sense that the sum of the energy fixed points is equal to that of the fixed points of its parts, and the sum is insensitive to the partitioning of the energy landscape. This means that the linear boundary perturbation created by the partitioning is relatively small as the quadratic area of the problem increases.<>