A neural architecture for the assignment problem: simulation and VLSI implementation

A competitive neural network architecture and hardware implementation is described. It is capable of solving first-order assignment problems. Each member of one set may be independently matched or blocked to a range of members of another set. One processing unit (PU) is used for each possible pairing of members, and analog association costs are applied directly to PU inputs as thresholds. Blocking constraints are enforced by circuits that oversee PU activations in each row and column, and modulate their excitations as required. Mean-field annealing is used to avoid local minima. Simulation results for problems to 64×64, with random costs, suggest that the hardware can be expected to settle in at most a few milliseconds. Since the simulation settled to the optimal solution in almost all cases it is apparent that the hardware can be expected to find at least good solutions. Characterization of an analog VLSI test chip implementing the PU and row/column constraint circuits is presented