Treatment of combinatorial optimization problems using selection equations with cost terms. Part I. Two-dimensional assignment problems

This paper is the first of two parts (Part II, Physica D 134 (1999) 242-252) which present a novel approach to the solution of assignment problems using time continuous dynamical systems. This first part concentrates on the two-dimensional assignment problem of combinatorial optimization, while in the second part the NP-hard three-dimensional problem is treated. The proposed dynamical system approach works by using coupled selection equations with cost terms. This is a combination of two basic ideas, namely first, coupled selection processes with suitably chosen initial values, where the dynamical system has suitable asymptotically stable points which represent the feasible solutions of the assignment problem. It is an important fact that there are feasible solutions only and no spurious states in this system. The second idea is based on the appropriate distortion of the basins of attraction of the asymptotically stable points by cost terms similar to classical penalty methods. (C) 1999 Elsevier Science B.V, All rights reserved.