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

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.