A neural computation approach to the set covering problem
Tal Grossman · University of North Texas Digital Library (University of North Texas) · 1995
This paper presents a neural network algorithm which is capable of finding approximate solutions for unicost set covering problems. The network has two types of units (neurons), with different dynamics and activation functions. One type represents the objects to be covered (the rows in the matrix representation of the problem) and another represents the ``covering`` sets (the 0,1 variables). They are connected as a bipartite graph which represents the incidence relations between objects and sets (i.e the 0,1 adjacency matrix). When the parameters of the units are correctly tuned, the stable states of the system correspond to the minimal covers. I show that in its basic mode of operation, descent dynamics, when the network is set in an arbitrary initial state it converges in less than 2n steps (where n is the number of variables), to a stable state which represents a valid solution. In this mode, the network implements a greedy heuristic in which the choice function is based on the unit inputs (which are determined by the activation functions and the network state). On top of the basic network dynamics, the algorithm applies an adaptive restart procedure which helps to search more effectively for ``good`` initial states and results in better performance.