OPTIMAL HOPFIELD NETWORK FOR COMBINATORIAL OPTIMIZATION WITH LINEAR COST FUNCTION

An ''optimal'' Hopfield network is presented for many of combinatorial optimization problems with linear cost function. It is proved that a vertex of the network state hypercube is asymptotically stable if and only if it is an optimal solution to the problem, That is, one can alw ays obtain an optimal solution whenever the network converges to a ver tex. In this sense, this network can be called the ''optimal'' Hopfiel d network. It is also shown through simulations of assignment problems that this network obtains optimal or nearly optimal solutions more fr equently than other familiar Hopfield networks.