Note—A Computational Survey of Methods for the Set Covering Problem

Abstract

This paper is a survey of available methods for the solution of the Set Covering Problem. The prime objective has been to establish the computational efficiency and relative merits of the various algorithms that have been proposed. To this end five methods have been programmed and tested on the same set of 33 test problems some of which can be found in the literature and the rest of which were randomly generated. Some of the methods examined have—as far as the authors are aware—never been previously tested, and in some cases some surprising results have been noted. In addition, one type of tree search method has been studied in some greater detail and new techniques involving multiple dominance tests, and the calculation of a better lower bound have been suggested to limit the search. This resulting algorithm was found to be better than the original one by orders of magnitude in both computation times and numbers of tree-nodes generated, and has proved to be the most efficient of the methods tested.