Hybrid heuristics for minimum cardinality set covering problems. (English) Zbl 0592.90065

Vasko, Francis J.; Wilson, George R.

Nav. Res. Logist. Q. 33, 241-249 (1986).

Summary: Minimum cardinality set covering problems (MCSCP) tend to be more difficult to solve than weighted set covering problems because the cost or weight associated with each variable is the same. Since MCSCP is NP- complete, large problem instances are commonly solved using some form of a greedy heuristic. In this paper hybrid algorithms are developed and tested against two common forms of the greedy heuristic. Although all the algorithms tested have the same worst case bounds provided by A. C. Ho [Math. Program. 23, 170-180 (1982; Zbl 0489.90066)], empirical results for 60 large randomly generated problems indicate that one algorithm performed better than the others.

MSC:

90C09	Boolean programming
65K05	Numerical mathematical programming methods
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

Minimum cardinality set covering; NP-complete; greedy heuristic

Citations:

Zbl 0489.90066

References:

[1]	Baker, Computers and Operations Research 8 pp 303– (1981)
[2]	and , ”Set Covering Algorithms Using Cutting Planes, Heuristics, and Subgradient Optimization: A Computational Study,” Mathematical Programming Study 12, North-Holland, Amsterdam, 1980, pp. 37–60. · Zbl 0435.90074
[3]	”On Maximum Matching, Minimum Covering, and Their Connections,” Proceedings of the International Symposium on Mathematical Programming, Ed., Princeton University Press, Princeton, NJ, 1970, pp. 303–311.
[4]	and , ”Set Covering by Ordinal Cuts I: Linear Objective Functions,” M. S. Research Report No. 321, Graduate School of Industrial Administration, Carnegie-Mellon University, 1973.
[5]	Chvatal, Mathematics of Operations Research 4 pp 233– (1979)
[6]	Cornuejols, Management Science 23 pp 789– (1977)
[7]	Ho, Mathematical Programming 23 pp 170– (1982)
[8]	Johnson, Journal of Computer and System Sciences 9 pp 256– (1974)
[9]	”Reducibility Among Combinatiorial Problems,” Complexity of Computer Computations, and , Eds., Plenum, New York, 1972.
[10]	Lemke, Operations Research 19 pp 978– (1971)
[11]	Marsten, Management Science 20 pp 774– (1974)
[12]	Marsten, Networks 11 pp 165– (1981)
[13]	”On The Set Representation and Set Covering Problem,” in Symposium on The Theory of Scheduling and Its Applications, Ed., Springer-Verlag, Heidelberg, 1973.
[14]	Salkin, ACM Journal 20 pp 189– (1973)
[15]	”An Efficient Heuristic for Large-Scale Facility Location-Type Problems with Applications in the Steel Industry,” Ph.D. dissertation, Lehigh University, 1983.
[16]	Vasko, Naval Research Logistics Quarterly 31 pp 163– (1984)