Load balancing loosely synchronous problems with a neural network
Geoffrey Fox, Wojtek Furmanski · 1988
Hopfield and Tank have introduced the use of neural networks for the solution of optimization problems such as the traveling salesman problem. Here we show how to generalize this method to decompose loosely synchronous problems onto parallel machines and in particular the hypercube. In this case, decomposition or load balancing can be formulated graph theoretically in terms of optimal partitioning of the computational graph into N = 2d subgraphs. The algorithm has a suggestive spin system interpretation, with the ferromagnetic interaction minimizing the communication and the long range paramagnetic force balancing the load. The optimal fixed point of the network is in the Higgs phase of the magnet, with the domains of constant spontaneous magnetization representing the optimal decomposition map.