American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Bilevel multi-objective construction site security planning with twofold random phenomenon
  • JIMO Home
  • This Issue
  • Next Article
    Optimality conditions for strong vector equilibrium problems under a weak constraint qualification
April  2015, 11(2): 575-594. doi: 10.3934/jimo.2015.11.575

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

Belma Yelbay 1, , Ş. İlker Birbil 2, and  Kerem Bülbül 2,

1. 

Sabancl University, Manufacturing Systems and Industrial Engineering, Orhanl1-Tuzla, 34956 Istanbul, Turkey
2. 

Sabanci University, Manufacturing Systems and Industrial Engineering, Orhanli-Tuzla, 34956 Istanbul, Turkey, Turkey

Received  September 2013 Revised  April 2014 Published  September 2014

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: LP relaxation, primal-dual heuristic, Heuristics, dual information., set covering.
Mathematics Subject Classification: Primary: 90C27; Secondary: 68T2.
Citation: Belma Yelbay, Ş. İlker Birbil, Kerem Bülbül. The set covering problem revisited: An empirical study of the value of dual information. Journal of Industrial & Management Optimization, 2015, 11 (2) : 575-594. doi: 10.3934/jimo.2015.11.575
References:
[1]

U. Aickelin, An indirect genetic algorithm for set covering problems,, Journal of the Operations Research, 53 (2002), 1118.  doi: 10.1057/palgrave.jors.2601317.  Google Scholar

[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.  doi: 10.1016/j.ejor.2010.01.035.  Google Scholar

[3]

E. Balas and M. C. Carrera, A dynamic subgradient-based branch-and-bound procedure for set covering,, Operations Research, 44 (1996), 875.  doi: 10.1287/opre.44.6.875.  Google Scholar

[4]

R. Bar-Yehuda and S. Even, A linear-time approximation algorithm for the weighted vertex cover problem,, Journal of Algorithms, 2 (1981), 198.  doi: 10.1016/0196-6774(81)90020-1.  Google Scholar

[5]

R. Bar-Yehuda and S. Even, On approximating a vertex cover for planar graphs,, in 14th ACM Symposium on Theory of Computing, (1982), 303.  doi: 10.1145/800070.802205.  Google Scholar

[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.  doi: 10.1137/050625382.  Google Scholar

[7]

J. E. Beasley, An algorithm for set covering problem,, European Journal of Operational Research, 31 (1987), 85.  doi: 10.1016/0377-2217(87)90141-X.  Google Scholar

[8]

J. E. Beasley, A Lagrangian heuristic for set covering problems,, Naval Research Logistics, 37 (1990), 151.  doi: 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2.  Google Scholar

[9]

J. E. Beasley and P. C. Chu, A genetic algorithm for the set covering problem,, European Journal of Operational Research, 94 (1996), 392.  doi: 10.1016/0377-2217(95)00159-X.  Google Scholar

[10]

J. E. Beasley and K. Jornsten, Enhancing an algorithm for set covering problems,, European Journal of Operational Research, 58 (1992), 293.  doi: 10.1016/0377-2217(92)90215-U.  Google Scholar

[11]

D. Bertsimas and R. Vohra, Rounding algorithms for covering problems,, Mathematical Programming, 80 (1998), 63.  doi: 10.1007/BF01582131.  Google Scholar

[12]

H. Brönnimann and M. Goodrich, Almost optimal set covers in finite vc-dimension,, Discrete and Computational Geometry, 14 (1995), 463.  doi: 10.1007/BF02570718.  Google Scholar

[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.  doi: 10.1023/A:1018900128545.  Google Scholar

[14]

A. Caprara, M. Fischetti and P. Toth, A heuristic method for the set covering problem,, Operations Research, 47 (1999), 730.  doi: 10.1287/opre.47.5.730.  Google Scholar

[15]

A. Caprara, P. Toth and M. Fischetti, Algorithms for the set covering problem,, Annals of Operations Research, 98 (2000), 353.  doi: 10.1023/A:1019225027893.  Google Scholar

[16]

M. Caserta, Metaheuristics: Progress in Complex Systems Optimization, 43-63,, Springer, (2007).   Google Scholar

[17]

S. Ceria, P. Nobili and A. Sassano, A Lagrangian-based heuristic for large-scale set covering problems,, Mathematical Programmimg, 81 (1998), 215.  doi: 10.1007/BF01581106.  Google Scholar

[18]

V. Chvatal, A greedy-heuristic for the set covering problem,, Mathematics of Operations Research, 4 (1979), 233.  doi: 10.1287/moor.4.3.233.  Google Scholar

[19]

G. Even, D. Rawitz and S. Shahar, Hitting sets when the vc-dimension is small,, Information Processing Letters, 95 (2005), 358.  doi: 10.1016/j.ipl.2005.03.010.  Google Scholar

[20]

T. A. Feo and M. Resende, A probabilistic heuristic for a computationally difficult set covering problem,, Operations Research Letters, 8 (1989), 67.  doi: 10.1016/0167-6377(89)90002-3.  Google Scholar

[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.  doi: 10.1007/3-540-46004-7_7.  Google Scholar

[22]

M. L. Fisher and P. Kedia, Optimal solution of set covering/partitioning problems using dual heuristics,, Management Science, 36 (1990), 674.  doi: 10.1287/mnsc.36.6.674.  Google Scholar

[23]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,, Freeman, (1979).   Google Scholar

[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.  doi: 10.1016/j.cor.2005.03.030.  Google Scholar

[25]

T. Grossman and A. Wool, Computational experience with aproximation algorithms for the set covering problem,, European Journal of Operational Research, 101 (1997), 81.  doi: 10.1016/S0377-2217(96)00161-0.  Google Scholar

[26]

N. Hall and R. V. Vohra, Pareto optimality and a class of set covering heuristics,, Annals of Operations Research, 43 (1993), 279.  doi: 10.1007/BF02025298.  Google Scholar

[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.   Google Scholar

[28]

D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems,, SIAM Journal on Computing, 11 (1982), 555.  doi: 10.1137/0211045.  Google Scholar

[29]

IBM, 2013, IBM ILOG CPLEX, Optimizer performance benchmarks., ().   Google Scholar

[30]

L. W. Jacobs and M. J. Brusco, A local search heuristic for large set-covering problems,, Naval Research Logistics, 42 (1995), 1129.  doi: 10.1002/1520-6750(199510)42:7<1129::AID-NAV3220420711>3.0.CO;2-M.  Google Scholar

[31]

G. Kinney, J. W. Barnes and B. Colleti, A Group Theoretic Tabu Search Algorithm for Set Covering Problems,, Technical report, (7871).   Google Scholar

[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.  doi: 10.1016/j.ejor.2005.09.028.  Google Scholar

[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.   Google Scholar

[34]

C. Lund and M. Yannakakis, On the hardness of approximating minimization problems,, Journal of ACM, 41 (1994), 960.  doi: 10.1145/185675.306789.  Google Scholar

[35]

E. Marchiori and A. Steenbeek, An iterated heuristic algorithm for the set covering problem,, in Proceedings WAE'98 Saarbrücken, (1998), 1.   Google Scholar

[36]

V. Melkonian, New primal-dual algorithms for steiner tree problems,, Computers & Operations Research, 34 (2007), 2147.  doi: 10.1016/j.cor.2005.08.009.  Google Scholar

[37]

N. Musliu, Local search algorithm for unicost set covering problem,, Lecture Notes in Artificial Intelligence, 4031 (2006), 302.  doi: 10.1007/11779568_34.  Google Scholar

[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.  doi: 10.1287/ijoc.1090.0376.  Google Scholar

[39]

C. A. Oliveira and P. M. Pardalos, A survey of combinatorial optimization problems in multicast routing,, Computers & Operations Research, 32 (2005), 1953.  doi: 10.1016/j.cor.2003.12.007.  Google Scholar

[40]

, OR-lib, 2013,, , ().   Google Scholar

[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.  doi: 10.1016/j.cie.2010.02.011.  Google Scholar

[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.  doi: 10.1016/0167-6377(93)90050-Q.  Google Scholar

[43]

S. Umetani and M. Yagiura, Relaxation heuristics for the set covering problem,, Journal of the Operations Research Society of Japan, 50 (2007), 350.   Google Scholar

[44]

V. Vapnik, Statistical Learning Theory,, Wiley-Interscience, (1998).   Google Scholar

[45]

F. J. Vasko and G. R. Wilson, An efficient heuristic for large set covering problems,, Naval Research Logistics Quarterly, 31 (1984), 163.  doi: 10.1002/nav.3800310118.  Google Scholar

[46]

V. V. Vazirani, Theoretical aspects of computer science,, Springer, 2292 (2002), 198.  doi: 10.1007/3-540-45878-6_7.  Google Scholar

[47]

D. P. Williamson, The primal-dual method for approximation algorithms,, Mathematical Programming, 91 (2002), 447.  doi: 10.1007/s101070100262.  Google Scholar

[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.  doi: 10.1016/j.ejor.2004.10.018.  Google Scholar

[49]

B. Yelbay, Primal-dual Heuristics for Solving the Set Covering Problem,, Master's thesis, (2010).   Google Scholar

[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,, , ().   Google Scholar

show all references

References:
[1]

U. Aickelin, An indirect genetic algorithm for set covering problems,, Journal of the Operations Research, 53 (2002), 1118.  doi: 10.1057/palgrave.jors.2601317.  Google Scholar

[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.  doi: 10.1016/j.ejor.2010.01.035.  Google Scholar

[3]

E. Balas and M. C. Carrera, A dynamic subgradient-based branch-and-bound procedure for set covering,, Operations Research, 44 (1996), 875.  doi: 10.1287/opre.44.6.875.  Google Scholar

[4]

R. Bar-Yehuda and S. Even, A linear-time approximation algorithm for the weighted vertex cover problem,, Journal of Algorithms, 2 (1981), 198.  doi: 10.1016/0196-6774(81)90020-1.  Google Scholar

[5]

R. Bar-Yehuda and S. Even, On approximating a vertex cover for planar graphs,, in 14th ACM Symposium on Theory of Computing, (1982), 303.  doi: 10.1145/800070.802205.  Google Scholar

[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.  doi: 10.1137/050625382.  Google Scholar

[7]

J. E. Beasley, An algorithm for set covering problem,, European Journal of Operational Research, 31 (1987), 85.  doi: 10.1016/0377-2217(87)90141-X.  Google Scholar

[8]

J. E. Beasley, A Lagrangian heuristic for set covering problems,, Naval Research Logistics, 37 (1990), 151.  doi: 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2.  Google Scholar

[9]

J. E. Beasley and P. C. Chu, A genetic algorithm for the set covering problem,, European Journal of Operational Research, 94 (1996), 392.  doi: 10.1016/0377-2217(95)00159-X.  Google Scholar

[10]

J. E. Beasley and K. Jornsten, Enhancing an algorithm for set covering problems,, European Journal of Operational Research, 58 (1992), 293.  doi: 10.1016/0377-2217(92)90215-U.  Google Scholar

[11]

D. Bertsimas and R. Vohra, Rounding algorithms for covering problems,, Mathematical Programming, 80 (1998), 63.  doi: 10.1007/BF01582131.  Google Scholar

[12]

H. Brönnimann and M. Goodrich, Almost optimal set covers in finite vc-dimension,, Discrete and Computational Geometry, 14 (1995), 463.  doi: 10.1007/BF02570718.  Google Scholar

[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.  doi: 10.1023/A:1018900128545.  Google Scholar

[14]

A. Caprara, M. Fischetti and P. Toth, A heuristic method for the set covering problem,, Operations Research, 47 (1999), 730.  doi: 10.1287/opre.47.5.730.  Google Scholar

[15]

A. Caprara, P. Toth and M. Fischetti, Algorithms for the set covering problem,, Annals of Operations Research, 98 (2000), 353.  doi: 10.1023/A:1019225027893.  Google Scholar

[16]

M. Caserta, Metaheuristics: Progress in Complex Systems Optimization, 43-63,, Springer, (2007).   Google Scholar

[17]

S. Ceria, P. Nobili and A. Sassano, A Lagrangian-based heuristic for large-scale set covering problems,, Mathematical Programmimg, 81 (1998), 215.  doi: 10.1007/BF01581106.  Google Scholar

[18]

V. Chvatal, A greedy-heuristic for the set covering problem,, Mathematics of Operations Research, 4 (1979), 233.  doi: 10.1287/moor.4.3.233.  Google Scholar

[19]

G. Even, D. Rawitz and S. Shahar, Hitting sets when the vc-dimension is small,, Information Processing Letters, 95 (2005), 358.  doi: 10.1016/j.ipl.2005.03.010.  Google Scholar

[20]

T. A. Feo and M. Resende, A probabilistic heuristic for a computationally difficult set covering problem,, Operations Research Letters, 8 (1989), 67.  doi: 10.1016/0167-6377(89)90002-3.  Google Scholar

[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.  doi: 10.1007/3-540-46004-7_7.  Google Scholar

[22]

M. L. Fisher and P. Kedia, Optimal solution of set covering/partitioning problems using dual heuristics,, Management Science, 36 (1990), 674.  doi: 10.1287/mnsc.36.6.674.  Google Scholar

[23]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,, Freeman, (1979).   Google Scholar

[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.  doi: 10.1016/j.cor.2005.03.030.  Google Scholar

[25]

T. Grossman and A. Wool, Computational experience with aproximation algorithms for the set covering problem,, European Journal of Operational Research, 101 (1997), 81.  doi: 10.1016/S0377-2217(96)00161-0.  Google Scholar

[26]

N. Hall and R. V. Vohra, Pareto optimality and a class of set covering heuristics,, Annals of Operations Research, 43 (1993), 279.  doi: 10.1007/BF02025298.  Google Scholar

[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.   Google Scholar

[28]

D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems,, SIAM Journal on Computing, 11 (1982), 555.  doi: 10.1137/0211045.  Google Scholar

[29]

IBM, 2013, IBM ILOG CPLEX, Optimizer performance benchmarks., ().   Google Scholar

[30]

L. W. Jacobs and M. J. Brusco, A local search heuristic for large set-covering problems,, Naval Research Logistics, 42 (1995), 1129.  doi: 10.1002/1520-6750(199510)42:7<1129::AID-NAV3220420711>3.0.CO;2-M.  Google Scholar

[31]

G. Kinney, J. W. Barnes and B. Colleti, A Group Theoretic Tabu Search Algorithm for Set Covering Problems,, Technical report, (7871).   Google Scholar

[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.  doi: 10.1016/j.ejor.2005.09.028.  Google Scholar

[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.   Google Scholar

[34]

C. Lund and M. Yannakakis, On the hardness of approximating minimization problems,, Journal of ACM, 41 (1994), 960.  doi: 10.1145/185675.306789.  Google Scholar

[35]

E. Marchiori and A. Steenbeek, An iterated heuristic algorithm for the set covering problem,, in Proceedings WAE'98 Saarbrücken, (1998), 1.   Google Scholar

[36]

V. Melkonian, New primal-dual algorithms for steiner tree problems,, Computers & Operations Research, 34 (2007), 2147.  doi: 10.1016/j.cor.2005.08.009.  Google Scholar

[37]

N. Musliu, Local search algorithm for unicost set covering problem,, Lecture Notes in Artificial Intelligence, 4031 (2006), 302.  doi: 10.1007/11779568_34.  Google Scholar

[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.  doi: 10.1287/ijoc.1090.0376.  Google Scholar

[39]

C. A. Oliveira and P. M. Pardalos, A survey of combinatorial optimization problems in multicast routing,, Computers & Operations Research, 32 (2005), 1953.  doi: 10.1016/j.cor.2003.12.007.  Google Scholar

[40]

, OR-lib, 2013,, , ().   Google Scholar

[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.  doi: 10.1016/j.cie.2010.02.011.  Google Scholar

[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.  doi: 10.1016/0167-6377(93)90050-Q.  Google Scholar

[43]

S. Umetani and M. Yagiura, Relaxation heuristics for the set covering problem,, Journal of the Operations Research Society of Japan, 50 (2007), 350.   Google Scholar

[44]

V. Vapnik, Statistical Learning Theory,, Wiley-Interscience, (1998).   Google Scholar

[45]

F. J. Vasko and G. R. Wilson, An efficient heuristic for large set covering problems,, Naval Research Logistics Quarterly, 31 (1984), 163.  doi: 10.1002/nav.3800310118.  Google Scholar

[46]

V. V. Vazirani, Theoretical aspects of computer science,, Springer, 2292 (2002), 198.  doi: 10.1007/3-540-45878-6_7.  Google Scholar

[47]

D. P. Williamson, The primal-dual method for approximation algorithms,, Mathematical Programming, 91 (2002), 447.  doi: 10.1007/s101070100262.  Google Scholar

[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.  doi: 10.1016/j.ejor.2004.10.018.  Google Scholar

[49]

B. Yelbay, Primal-dual Heuristics for Solving the Set Covering Problem,, Master's thesis, (2010).   Google Scholar

[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,, , ().   Google Scholar

[1]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169
[2]

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161
[3]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[4]

Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (81)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences