Inhibitory grids and the assignment problem

Author

Wolfe, William J. ; MacMillan, James M. ; Brady, George ; Mathews, Robert ; Rothman, Jay Alan ; Mathis, Donald ; Orosz, Michael Donald ; Anderson, Charlie ; Alaghban, Gila

Author_Institution

Dept. of Comput. Sci. & Eng., Colorado Univ., Denver, CO, USA

Volume

4

Issue

2

fYear

1993

fDate

3/1/1993 12:00:00 AM

Firstpage

319

Lastpage

331

Abstract

A family of symmetric neural networks that solve a simple version of the assignment problem (AP) is analyzed. The authors analyze the suboptimal performance of these networks and compare the results to optimal answers obtained by linear programming techniques. They then use the interactive activation model to define the network dynamics-a model that is closely related to the Hopfield-Tank model. A systematic analysis of hypercube corner stability and eigenspaces of the connection strength matrix leads to network parameters that give feasible solutions 100% of the time and to a projection algorithm that significantly improves performance. Two formulations of the problem are discussed: (i) nearest corner: encode the assignment numbers as initial activations, and (ii) lowest energy corner: encode the assignment numbers as external inputs

Keywords

eigenvalues and eigenfunctions; matrix algebra; neural nets; operations research; Hopfield-Tank model; assignment problem; connection strength matrix; eigenspaces; hypercube corner stability; interactive activation model; network dynamics; operations research; symmetric neural networks; Algorithm design and analysis; Analog circuits; Computer science; Hypercubes; Linear programming; Neural networks; Performance analysis; Projection algorithms; Random number generation; Stability analysis;

fLanguage

English

Journal_Title

Neural Networks, IEEE Transactions on

Publisher

ieee

ISSN

1045-9227

Type

jour

DOI

10.1109/72.207619

Filename

207619