The set covering problem revisited: an empirical study of the value of dual information.

*(English)*Zbl 1304.90182Summary: This paper investigates the role of dual information on the performances of heuristics designed for solving the set covering problem. After solving the linear programming relaxation of the problem, the dual information is used to obtain the two main approaches proposed here: (i) The size of the original problem is reduced and then the resulting model is solved with exact methods. We demonstrate the effectiveness of this approach on a rich set of benchmark instances compiled from the literature. We conclude that set covering problems of various characteristics and sizes may reliably be solved to near optimality without resorting to custom solution methods. (ii) The dual information is embedded into an existing heuristic. This approach is demonstrated on a well-known local search based heuristic that was reported to obtain successful results on the set covering problem. Our results demonstrate that the use of dual information significantly improves the efficacy of the heuristic in terms of both solution time and accuracy.

##### MSC:

90C27 | Combinatorial optimization |

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

##### Software:

CPLEX
PDF
BibTeX
XML
Cite

\textit{B. Yelbay} et al., J. Ind. Manag. Optim. 11, No. 2, 575--594 (2015; Zbl 1304.90182)

Full Text:
DOI

##### References:

[1] | U. Aickelin, An indirect genetic algorithm for set covering problems,, Journal of the Operations Research, 53, 1118, (2002) · Zbl 1139.90428 |

[2] | Z. N. Azimi, An electromagnetism metaheuristic for the unicost set covering problem,, European Journal of Operational Research, 205, 290, (2010) · Zbl 1188.90218 |

[3] | E. Balas, A dynamic subgradient-based branch-and-bound procedure for set covering,, Operations Research, 44, 875, (1996) · Zbl 0879.90155 |

[4] | R. Bar-Yehuda, A linear-time approximation algorithm for the weighted vertex cover problem,, Journal of Algorithms, 2, 198, (1981) · Zbl 0459.68033 |

[5] | R. Bar-Yehuda, On approximating a vertex cover for planar graphs,, in 14th ACM Symposium on Theory of Computing, 303, (1982) |

[6] | R. Bar-Yehuda, On the equivalence between the primal-dual schema and the local ratio technique,, SIAM Journal on Discrete Mathematics, 19, 762, (2005) · Zbl 1096.68164 |

[7] | J. E. Beasley, An algorithm for set covering problem,, European Journal of Operational Research, 31, 85, (1987) · Zbl 0679.90039 |

[8] | J. E. Beasley, A Lagrangian heuristic for set covering problems,, Naval Research Logistics, 37, 151, (1990) · Zbl 0684.90063 |

[9] | J. E. Beasley, A genetic algorithm for the set covering problem,, European Journal of Operational Research, 94, 392, (1996) · Zbl 0953.90565 |

[10] | J. E. Beasley, Enhancing an algorithm for set covering problems,, European Journal of Operational Research, 58, 293, (1992) · Zbl 0759.90070 |

[11] | D. Bertsimas, Rounding algorithms for covering problems,, Mathematical Programming, 80, 63, (1998) · Zbl 0894.90121 |

[12] | H. Brönnimann, Almost optimal set covers in finite vc-dimension,, Discrete and Computational Geometry, 14, 463, (1995) · Zbl 0841.68122 |

[13] | M. J. Brusco, A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems,, Annals of Operations Research, 86, 611, (1999) · Zbl 0922.90112 |

[14] | A. Caprara, A heuristic method for the set covering problem,, Operations Research, 47, 730, (1999) · Zbl 0976.90086 |

[15] | A. Caprara, Algorithms for the set covering problem,, Annals of Operations Research, 98, 353, (2000) · Zbl 0974.90006 |

[16] | M. Caserta, <em>Metaheuristics: Progress in Complex Systems Optimization</em>, 43-63,, Springer, (2007) |

[17] | S. Ceria, A Lagrangian-based heuristic for large-scale set covering problems,, Mathematical Programmimg, 81, 215, (1998) · Zbl 0919.90085 |

[18] | V. Chvatal, A greedy-heuristic for the set covering problem,, Mathematics of Operations Research, 4, 233, (1979) · Zbl 0443.90066 |

[19] | G. Even, Hitting sets when the vc-dimension is small,, Information Processing Letters, 95, 358, (2005) · Zbl 1184.68632 |

[20] | T. A. Feo, A probabilistic heuristic for a computationally difficult set covering problem,, Operations Research Letters, 8, 67, (1989) · Zbl 0675.90073 |

[21] | M. Finger, Exploiting fitness distance correlation of set covering problems,, Lecture Notes in Computer Science, 2279, 61, (2002) · Zbl 1044.68757 |

[22] | M. L. Fisher, Optimal solution of set covering/partitioning problems using dual heuristics,, Management Science, 36, 674, (1990) · Zbl 0706.90048 |

[23] | M. R. Garey, <em>Computers and Intractability: A Guide to the Theory of NP-Completeness</em>,, Freeman, (1979) · Zbl 0411.68039 |

[24] | F. C. Gomes, Experimental analysis of approximation algorithms for the vertex cover and set covering problems,, Computers & Operations Research, 33, 3520, (2006) · Zbl 1110.90083 |

[25] | T. Grossman, Computational experience with aproximation algorithms for the set covering problem,, European Journal of Operational Research, 101, 81, (1997) · Zbl 0929.90072 |

[26] | N. Hall, Pareto optimality and a class of set covering heuristics,, Annals of Operations Research, 43, 279, (1993) · Zbl 0784.90060 |

[27] | M. Haouari, A probabilistic greedy search algorithm for combinatorial optimization with application to the set covering problem,, Journal of the Operational Research Society, 53, 792, (2002) · Zbl 1130.90389 |

[28] | D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems,, SIAM Journal on Computing, 11, 555, (1982) · Zbl 0486.68067 |

[29] | IBM, IBM ILOG CPLEX, Optimizer performance benchmarks. |

[30] | L. W. Jacobs, A local search heuristic for large set-covering problems,, Naval Research Logistics, 42, 1129, (1995) · Zbl 0839.90085 |

[31] | G. Kinney, <em>A Group Theoretic Tabu Search Algorithm for Set Covering Problems</em>,, Technical report, (7871) |

[32] | G. Lan, An effective and simple heuristic for the set covering problem,, European Journal of Operational Research, 176, 1387, (2007) · Zbl 1102.90048 |

[33] | L. A. N. Lorena, Genetic algorithms applied to computationally difficult set covering problems,, Journal of Operational Research Society, 48, 440, (1997) · Zbl 0887.90119 |

[34] | C. Lund, On the hardness of approximating minimization problems,, Journal of ACM, 41, 960, (1994) · Zbl 0814.68064 |

[35] | E. Marchiori, An iterated heuristic algorithm for the set covering problem,, in Proceedings WAE’98 Saarbrücken, 1, (1998) |

[36] | V. Melkonian, New primal-dual algorithms for steiner tree problems,, Computers & Operations Research, 34, 2147, (2007) · Zbl 1112.90070 |

[37] | N. Musliu, Local search algorithm for unicost set covering problem,, Lecture Notes in Artificial Intelligence, 4031, 302, (2006) |

[38] | I. Muter, Combination of metaheuristic and exact algorithms for solving set covering-type optimization problems,, INFORMS Journal on Computing, 22, 603, (2010) · Zbl 1243.90257 |

[39] | C. A. Oliveira, A survey of combinatorial optimization problems in multicast routing,, Computers & Operations Research, 32, 1953, (2005) · Zbl 1068.90027 |

[40] | OR-lib, 2013,, <a href= |

[41] | Z. G. Ren, New ideas for applying ant colony optimization to the set covering problem,, Computers & Industrial Engineering, 58, 774, (2010) |

[42] | R. A. Rushmeier, Experiments with parallel branch-and-bound algorithms for the set covering problem,, Operations Research Letters, 13, 277, (1993) · Zbl 0789.90056 |

[43] | S. Umetani, Relaxation heuristics for the set covering problem,, Journal of the Operations Research Society of Japan, 50, 350, (2007) · Zbl 1142.90479 |

[44] | V. Vapnik, <em>Statistical Learning Theory</em>,, Wiley-Interscience, (1998) · Zbl 0935.62007 |

[45] | F. J. Vasko, An efficient heuristic for large set covering problems,, Naval Research Logistics Quarterly, 31, 163, (1984) · Zbl 0534.90064 |

[46] | V. V. Vazirani, Theoretical aspects of computer science,, Springer, 2292, 198, (2002) |

[47] | D. P. Williamson, The primal-dual method for approximation algorithms,, Mathematical Programming, 91, 447, (2002) · Zbl 1030.90111 |

[48] | M. Yagiura, A 3-flip neighborhood local search for the set covering problem,, European Journal of Operational Research, 172, 472, (2006) · Zbl 1120.90025 |

[49] | B. Yelbay, <em>Primal-dual Heuristics for Solving the Set Covering Problem</em>,, Master’s thesis, (2010) |

[50] | B. Yelbay, Trade-offs computing minimum hub cover toward optimized graph query processing, 2013,, <a href= |

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.