Dynamical System Approaches to Combinatorial Optimization

This article describes and compares several dynamical system approaches to combinatorial optimization problems. These include penalty methods, the approach of Hopfield and Tank, self-organizing maps, i.e., Kohonen networks, coupled selection equations, and hybrid methods. Many of them are investigated analytically and the costs of the solutions are compared numerically with those of solutions obtained by simulated annealing and the costs of a global optimal solution. In order to get reproducible simulation results, a pseudo-random number generator with integer arithmetic is used to produce the data sets. Using dynamical systems, a solution to the combinatorial optimization problem emerges in the limit of large times as an asymptotically stable point of the dynamics. These are often not global optimal solutions but good approximations of it. Dynamical system and neural network approaches are appropriate methods for distributed and parallel processing. Because of the parallelization, these techniques are able to compute a given task much faster than algorithms which are using a traditional sequentially working digital computer. The analysis focuses on the linear two-dimensional (two-index) assignment problem and the NP-hard three-dimensional (three-index) assignment problem. These and other assignment problems can be used as models for many industrial problems like manufacturing planning and optimization of flexible manufacturing systems (FMS).