Dynamical System Approaches to Combinatorial Optimization

Several dynamical system approaches to combinatorial optimization problems are described and compared. These include dynamical systems derived from penalty methods; the approach of Hopfield and Tank; self-organizing maps, that is, 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.

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. The obtained solutions are often not globally optimal 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.

This chapter focuses on dynamical system approaches to the linear two-index assignment problem and the NP -hard three-index assignment problem. These and extensions thereof can be used as models for many industrial problems like manufacturing planning and optimization of flexible manufacturing systems. This is illustrated for an example in distributed robotic systems.