ANALYSIS AND DESIGN OF PRIMAL-DUAL ASSIGNMENT NETWORKS

The assignment problem is an archetypical combinatorial optimization p roblem having widespread applications, This paper presents two recurre nt neural networks, a continuous-time one and a discrete-time one, for solving the assignment problem, Because the proposed recurrent neural networks solve the primal and dual assignment problems simultaneously , they are named as the primal-dual assignment networks. The primal-du al assignment networks are guaranteed to make optimal assignment regar dless of initial conditions, Unlike the primal or dual assignment netw ork, there is no time-varying design parameter in the primal-dual assi gnment networks, Therefore, they are more suitable for hardware implem entation. The performance and operating characteristics of the primal- dual assignment networks are demonstrated by means of illustrative exa mples.