×

Using a facility location algorithm to solve large set covering problems. (English) Zbl 0543.90084

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.

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
PDFBibTeX XMLCite
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.