A neural network for the minimum set covering problem

We solve approximately the weighted set covering problem by putting togethe r a neural network model, the Boltzmann machine (BM), and some combinatoria l ideas. We compare the solutions provided by the network with the ones obt ained using the greedy set covering heuristic and the Lagrangian heuristic developed by Beasley. Moreover, we use a simple and intuitive polynomial de composition scheme treating large instances by decomposing them into smalle r ones. Finally, we report on the relation between the convergence time of the model and the size of the instances of set covering. (C) 2000 Elsevier Science Ltd. All rights reserved.