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

Nicos Christofides and S. Korman
Additional contact information
Nicos Christofides: Imperial College of Science and Technology, England
S. Korman: Imperial College of Science and Technology, England

Management Science, 1975, vol. 21, issue 5, 591-599

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.

Date: 1975
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.21.5.591 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:21:y:1975:i:5:p:591-599

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().