Research Reports from the Department of Operations
Document Type
Report
Publication Date
9-1-1975
Abstract
These pages discuss the code USETCO which contains an algorithm for the set covering problem. (That is, minimize cx, subject to Ex ≥ e, x≥0, and x integer; where E is an m by n matrix of 1's and 0's, and e is an m vector of 1's.) The special problem structure permits a rather efficient, yet simple, solution procedure which is basically a zero-one 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 and 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. A detailed description of the algorithm may be found in "Set Covering by Single-Branch Enumeration with Linear Programming Subproblems," by C. E. Lemke, H. M. Salkin, and K. Spielberg, Operations Research 19(4), 998-1022 (1971). Other related material is in Integer Programming, by H. M. Salkin, Addison-Wesley, 1975 (Chapter 7).
Keywords
Operations research, Combinatorial optimization, Algorithms, Linear programming, Integer programming, Mathematical optimization, Computer programs
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 392
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Salkin, Harvey M., "Set Covering Algorithm and Computer Program USETCO User's Manual" (1975). Research Reports from the Department of Operations. 514.
https://commons.case.edu/wsom-ops-reports/514