Treatment of combinatorial optimization problems using selection equationswith 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 usi ng time continuous dynamical systems. This first part concentrates on the t wo-dimensional assignment problem of combinatorial optimization, while in t he second part the NP-hard three-dimensional problem is treated. The propos ed dynamical system approach works by using coupled selection equations wit h cost terms. This is a combination of two basic ideas, namely first, coupl ed selection processes with suitably chosen initial values, where the dynam ical system has suitable asymptotically stable points which represent the f easible solutions of the assignment problem. It is an important fact that t here are feasible solutions only and no spurious states in this system. The second idea is based on the appropriate distortion of the basins of attrac tion of the asymptotically stable points by cost terms similar to classical penalty methods. (C) 1999 Elsevier Science B.V, All rights reserved.