A neural network for the minimum set covering problem

We solve approximately the weighted set covering problem by putting together a neural network model, the Boltzmann machine (BM), and some combinatorial ideas. We compare the solutions provided by the network with the ones obtained using the greedy set covering heuristic and the Lagrangian heuristic developed by Beasley. Moreover, we use a simple and intuitive polynomial decomposition scheme treating large instances by decomposing them into smaller 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.