Hybrid heuristic algorithms for set covering

Minimal set covering (MSC) is a known NP-hard problem. It is the model of many important real-world problems and plays a central role in rostering (crew scheduling) problems. Large-size set covering problems (constraint matrix of about 10,000*100,000 elements) are considered. First, the traditional model of MSC as integer program is recalled, then a new representation in linear programming (LP) is described. Finally, a new algorithm based on recurrent neural networks is introduced for the optimization of the pivot positions selection. This algorithm is combined with the LP algorithm to guarantee an optimal solution. The heuristic part serves for choosing the pivot positions in the Simplex algorithm for LP. The results of significant tests on real data are reported. They compare favourably with the best-known results on set covering, both in terms of execution time and solution accuracy.