zbMATH — the first resource for mathematics

An efficient heuristic for large set covering problems. (English) Zbl 0534.90064
This paper presents an efficient heuristic algorithm for solving large set covering problems that uses a random selection rule on several criteria in order to build solutions. Unlike other set covering heuristics which use the same criterion throughout the covering process, this new heuristic dynamically changes the selection criteria while building a cover. This algorithm and five heuristics in E. Balas and A. C. Ho [Math. Program. Study 12, 37-60 (1980; Zbl 0435.90074)] were used to solve 30 large randomly generated set covering problems. The best solution generated by the five heuristics was never better than the authors’ algorithm and, in fact, this algorithm was strictly better for 50% of the problems. When the solutions for the first 15 problems were compared to the optimum, this algorithm obtained the optimum for 13 of the 15 problems, whereas, the best solution of five heuristics was optimal for only 7 of the 15 problems.

90C10 Integer programming
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
65K05 Numerical mathematical programming methods
Full Text: DOI
[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] Chvatal, Mathematics of Operations Research 4 pp 233– (1979)
[4] Erlenkotter, Operations Research 26 pp 992– (1978)
[5] Fisher, Proceedings of the Cambridge Philosophical Society 24 pp 180– (1928)
[6] and , Integer Programming, Wiley, New York, 1972.
[7] Golden, Naval Research Logistics Quarterly 26 pp 69– (1979)
[8] Ho, Mathematical Programming 23 pp 170– (1982)
[9] ”Reducibility Among Combinatorial Problems,” Complexity of Computer Computations, and , Eds., Plenum, New York, 1972.
[10] private communication, July 1982.
[11] Roth, Operarions Research 17 pp 455– (1969)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.