Vasko, Francis J.; Wilson, George R. Using a facility location algorithm to solve large set covering problems. (English) Zbl 0543.90084 Oper. Res. Lett. 3, 85-90 (1984). Summary: D. Erlenkotter [Oper. Res. 26, 992-1009 (1978; Zbl 0422.90053)] has developed an efficient exact (guarantees optimality) algorithm to solve the uncapacitated facility location problem (UFLP). In this paper, we use his algorithm to solve large instances of an important subset of the UFLP; the set covering problem (SCP). In addition, we present further empirical evidence that a heuristic algorithm developed by the authors [Nav. Res. Logist. Q. 31, 163-171 (1984; Zbl 0534.90064)] for the SCP is capable of quickly generating good solutions to large SCP’s. Cited in 10 Documents MSC: 90C10 Integer programming 65K05 Numerical mathematical programming methods 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 90B05 Inventory, storage, reservoirs 68Q25 Analysis of algorithms and problem complexity Keywords:large-scale problems; combinatorial optimization; uncapacitated facility location problem; set covering; heuristic algorithm Citations:Zbl 0422.90053; Zbl 0534.90064 PDFBibTeX XMLCite \textit{F. J. Vasko} and \textit{G. R. Wilson}, Oper. Res. Lett. 3, 85--90 (1984; Zbl 0543.90084) Full Text: DOI References: [1] Baker, E., Heuristic algorithms for the weighted set covering problem, Computer and Operations Research, 8, 4, 303-310 (1981) [2] Balas, E.; Ho, A. C., Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study, (Mathematical Programming Study, 12 (1980), North-Holland Publishing Company), 37-60 · Zbl 0435.90074 [3] Chvatal, V., A greedy heuristic for the set-covering problem, Mathematic of Operations Research, 4, 3, 233-235 (1979) · Zbl 0443.90066 [4] Cornuejols, G.; Fisher, M. L.; Nemhauser, G. L., Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms, Management Science, 23, 12, 1273-1283 (1977) · Zbl 0361.90034 [5] Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Operations Research, 26, 6, 992-1009 (1978) · Zbl 0422.90053 [6] Ho, A. C., Worst case analysis of a class of set covering heuristics, Mathematical Programming, 23, 2, 170-180 (1982) · Zbl 0489.90066 [7] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York) · Zbl 0366.68041 [8] Roth, R., Computer solutions to minimum-cover problems, Operations Research, 455-465 (1969) · Zbl 0174.20706 [9] Vasko, F. J., An efficient heuristic for large-scale facility location-type problems with applications in the steel industry, (Ph.D. dissertation (1983), Lehigh University) [10] Vasko, F. J.; Wilson, G. R., An efficient heuristic for large set covering problems, Naval Research Logistics Quarterly, 31, 1, 163-171 (1984) · Zbl 0534.90064 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.