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

Belma Yelbay; Ş. İlker Birbil; Kerem Bülbül

doi:10.3934/jimo.2015.11.575

Article Contents

2015, Volume 11, Issue 2: 575-594. Doi: 10.3934/jimo.2015.11.575

This issue Previous Article Optimality conditions for strong vector equilibrium problems under a weak constraint qualification Next Article Bilevel multi-objective construction site security planning with twofold random phenomenon

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

1.
Sabancl University, Manufacturing Systems and Industrial Engineering, Orhanl1-Tuzla, 34956 Istanbul
2.
Sabanci University, Manufacturing Systems and Industrial Engineering, Orhanli-Tuzla, 34956 Istanbul

Received: August 31, 2013

Revised: March 31, 2014

Published: March 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C27; Secondary: 68T20.

Citation:

Related Papers

Cited by

References

[1]	U. Aickelin, An indirect genetic algorithm for set covering problems, Journal of the Operations Research, 53 (2002), 1118-1126.doi: 10.1057/palgrave.jors.2601317.
[2]	Z. N. Azimi, P. Toth and L. Galli, An electromagnetism metaheuristic for the unicost set covering problem, European Journal of Operational Research, 205 (2010), 290-300.doi: 10.1016/j.ejor.2010.01.035.
[3]	E. Balas and M. C. Carrera, A dynamic subgradient-based branch-and-bound procedure for set covering, Operations Research, 44 (1996), 875-890.doi: 10.1287/opre.44.6.875.
[4]	R. Bar-Yehuda and S. Even, A linear-time approximation algorithm for the weighted vertex cover problem, Journal of Algorithms, 2 (1981), 198-203.doi: 10.1016/0196-6774(81)90020-1.
[5]	R. Bar-Yehuda and S. Even, On approximating a vertex cover for planar graphs, in 14th ACM Symposium on Theory of Computing, San Francisco, California, (1982), 303-309.doi: 10.1145/800070.802205.
[6]	R. Bar-Yehuda and D. Rawitz, On the equivalence between the primal-dual schema and the local ratio technique, SIAM Journal on Discrete Mathematics, 19 (2005), 762-797.doi: 10.1137/050625382.
[7]	J. E. Beasley, An algorithm for set covering problem, European Journal of Operational Research, 31 (1987), 85-93.doi: 10.1016/0377-2217(87)90141-X.
[8]	J. E. Beasley, A Lagrangian heuristic for set covering problems, Naval Research Logistics, 37 (1990), 151-164.doi: 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2.
[9]	J. E. Beasley and P. C. Chu, A genetic algorithm for the set covering problem, European Journal of Operational Research, 94 (1996), 392-404.doi: 10.1016/0377-2217(95)00159-X.
[10]	J. E. Beasley and K. Jornsten, Enhancing an algorithm for set covering problems, European Journal of Operational Research, 58 (1992), 293-300.doi: 10.1016/0377-2217(92)90215-U.
[11]	D. Bertsimas and R. Vohra, Rounding algorithms for covering problems, Mathematical Programming, 80 (1998), 63-89.doi: 10.1007/BF01582131.
[12]	H. Brönnimann and M. Goodrich, Almost optimal set covers in finite vc-dimension, Discrete and Computational Geometry, 14 (1995), 463-479.doi: 10.1007/BF02570718.
[13]	M. J. Brusco, L. W. Jacobs and G. M. Thompson, A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems, Annals of Operations Research, 86 (1999), 611-627.doi: 10.1023/A:1018900128545.
[14]	A. Caprara, M. Fischetti and P. Toth, A heuristic method for the set covering problem, Operations Research, 47 (1999), 730-743.doi: 10.1287/opre.47.5.730.
[15]	A. Caprara, P. Toth and M. Fischetti, Algorithms for the set covering problem, Annals of Operations Research, 98 (2000), 353-371.doi: 10.1023/A:1019225027893.
[16]	M. Caserta, Metaheuristics: Progress in Complex Systems Optimization, 43-63, Springer, Berlin, 2007.
[17]	S. Ceria, P. Nobili and A. Sassano, A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programmimg, 81 (1998), 215-228.doi: 10.1007/BF01581106.
[18]	V. Chvatal, A greedy-heuristic for the set covering problem, Mathematics of Operations Research, 4 (1979), 233-235.doi: 10.1287/moor.4.3.233.
[19]	G. Even, D. Rawitz and S. Shahar, Hitting sets when the vc-dimension is small, Information Processing Letters, 95 (2005), 358-362.doi: 10.1016/j.ipl.2005.03.010.
[20]	T. A. Feo and M. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters, 8 (1989), 67-71.doi: 10.1016/0167-6377(89)90002-3.
[21]	M. Finger, T. Stützle and H. Lourenço, Exploiting fitness distance correlation of set covering problems, Lecture Notes in Computer Science, 2279 (2002), 61-71.doi: 10.1007/3-540-46004-7_7.
[22]	M. L. Fisher and P. Kedia, Optimal solution of set covering/partitioning problems using dual heuristics, Management Science, 36 (1990), 674-688.doi: 10.1287/mnsc.36.6.674.
[23]	M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.
[24]	F. C. Gomes, C. N. Meneses, P. M. Pardalos and G. V. R. Viana, Experimental analysis of approximation algorithms for the vertex cover and set covering problems, Computers & Operations Research, 33 (2006), 3520-3534.doi: 10.1016/j.cor.2005.03.030.
[25]	T. Grossman and A. Wool, Computational experience with aproximation algorithms for the set covering problem, European Journal of Operational Research, 101 (1997), 81-92.doi: 10.1016/S0377-2217(96)00161-0.
[26]	N. Hall and R. V. Vohra, Pareto optimality and a class of set covering heuristics, Annals of Operations Research, 43 (1993), 279-284.doi: 10.1007/BF02025298.
[27]	M. Haouari and J. S. Chaouachi, A probabilistic greedy search algorithm for combinatorial optimization with application to the set covering problem, Journal of the Operational Research Society, 53 (2002), 792-799.
[28]	D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems, SIAM Journal on Computing, 11 (1982), 555-556.doi: 10.1137/0211045.
[29]	IBM, 2013, IBM ILOG CPLEX Optimizer performance benchmarks.
[30]	L. W. Jacobs and M. J. Brusco, A local search heuristic for large set-covering problems, Naval Research Logistics, 42 (1995), 1129-1140.doi: 10.1002/1520-6750(199510)42:7<1129::AID-NAV3220420711>3.0.CO;2-M.
[31]	G. Kinney, J. W. Barnes and B. Colleti, A Group Theoretic Tabu Search Algorithm for Set Covering Problems, Technical report, Graduate Program in Operations Research and Industrial Engineering, The University of Texas, Austin, Texas 78712, 2004.
[32]	G. Lan, G. W. DePuy and G. E. Whitehouse, An effective and simple heuristic for the set covering problem, European Journal of Operational Research, 176 (2007), 1387-1403.doi: 10.1016/j.ejor.2005.09.028.
[33]	L. A. N. Lorena and L. S. Lopes, Genetic algorithms applied to computationally difficult set covering problems, Journal of Operational Research Society, 48 (1997), 440-445.
[34]	C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Journal of ACM, 41 (1994), 960-981.doi: 10.1145/185675.306789.
[35]	E. Marchiori and A. Steenbeek, An iterated heuristic algorithm for the set covering problem, in Proceedings WAE'98 Saarbrücken, (1998), 1-3.
[36]	V. Melkonian, New primal-dual algorithms for steiner tree problems, Computers & Operations Research, 34 (2007), 2147-2167.doi: 10.1016/j.cor.2005.08.009.
[37]	N. Musliu, Local search algorithm for unicost set covering problem, Lecture Notes in Artificial Intelligence, 4031 (2006), 302-311.doi: 10.1007/11779568_34.
[38]	I. Muter, S. I. Birbil and G. Sahin, Combination of metaheuristic and exact algorithms for solving set covering-type optimization problems, INFORMS Journal on Computing, 22 (2010), 603-619.doi: 10.1287/ijoc.1090.0376.
[39]	C. A. Oliveira and P. M. Pardalos, A survey of combinatorial optimization problems in multicast routing, Computers & Operations Research, 32 (2005), 1953-1981, URL http://www.sciencedirect.com/science/article/pii/S0305054803003873.doi: 10.1016/j.cor.2003.12.007.
[40]	OR-lib, 2013, http://people.brunel.ac.uk/~ mastjjb/jeb/info.html.
[41]	Z. G. Ren, Z. R. Feng, L. J. Ke and Z. J. Zhang, New ideas for applying ant colony optimization to the set covering problem, Computers & Industrial Engineering, 58 (2010), 774-784.doi: 10.1016/j.cie.2010.02.011.
[42]	R. A. Rushmeier and G. L. Nemhauser, Experiments with parallel branch-and-bound algorithms for the set covering problem, Operations Research Letters, 13 (1993), 277-285.doi: 10.1016/0167-6377(93)90050-Q.
[43]	S. Umetani and M. Yagiura, Relaxation heuristics for the set covering problem, Journal of the Operations Research Society of Japan, 50 (2007), 350-375.
[44]	V. Vapnik, Statistical Learning Theory, Wiley-Interscience, 1998.
[45]	F. J. Vasko and G. R. Wilson, An efficient heuristic for large set covering problems, Naval Research Logistics Quarterly, 31 (1984), 163-171.doi: 10.1002/nav.3800310118.
[46]	V. V. Vazirani, Theoretical aspects of computer science, Springer, Verlag LNCS, 2292 (2002), 198-207.doi: 10.1007/3-540-45878-6_7.
[47]	D. P. Williamson, The primal-dual method for approximation algorithms, Mathematical Programming, 91 (2002), 447-478.doi: 10.1007/s101070100262.
[48]	M. Yagiura, M. Kishida and T. Ibaraki, A 3-flip neighborhood local search for the set covering problem, European Journal of Operational Research, 172 (2006), 472-499.doi: 10.1016/j.ejor.2004.10.018.
[49]	B. Yelbay, Primal-dual Heuristics for Solving the Set Covering Problem, Master's thesis, Sabanci University, Istanbul,Turkey, 2010.
[50]	B. Yelbay, S. I. Birbil, K. Bülbül and H. Jamil, Trade-offs computing minimum hub cover toward optimized graph query processing, 2013, http://arxiv.org/abs/1311.1626.