Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems

C. E. Lemke, H. M. Salkin and K. Spielberg
Additional contact information
C. E. Lemke: Rensselaer Polytechnic Institute, Troy, New York
H. M. Salkin: Case Western Reserve University, Cleveland, Ohio
K. Spielberg: IBM Research Center, Yorktown Heights, New York

Operations Research, 1971, vol. 19, issue 4, 998-1022

Abstract: This paper presents an algorithm for the set-covering problem (that is, min c ′ y : Ey ≧ e , y ≧ 0, y i integer, where E is an m by n matrix of l's and 0's, and e is an m -vector of l's). The special problem structure permits a rather efficient, yet simple, solution procedure that is basically a (0, 1) search of the single-branch type coupled with linear programming and a suboptimization technique. The algorithm has been found to be highly effective for a good number of relatively large problems. Problems from 30 to 905 variables with as many as 200 rows have been solved in less than 16 minutes on an IBM 360 Model 50 computer. The algorithm's effectiveness stems from an efficient suboptimization procedure, which constructs excellent integer solutions from the solutions to linear-programming subproblems.

Date: 1971
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.19.4.998 (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:oropre:v:19:y:1971:i:4:p:998-1022

Access Statistics for this article

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