A Meta-Heuristic Algorithm for Set Covering Problem Based on Gravity

Authors: S. Raja Balachandar, K. Kannan

Abstract:

A new Meta heuristic approach called "Randomized gravitational emulation search algorithm (RGES)" for solving large size set covering problems has been designed. This algorithm is found upon introducing randomization concept along with the two of the four primary parameters -velocity- and -gravity- in physics. A new heuristic operator is introduced in the domain of RGES to maintain feasibility specifically for the set covering problem to yield best solutions. The performance of this algorithm has been evaluated on a large set of benchmark problems from OR-library. Computational results showed that the randomized gravitational emulation search algorithm - based heuristic is capable of producing high quality solutions. The performance of this heuristic when compared with other existing heuristic algorithms is found to be excellent in terms of solution quality.

Keywords: Set covering problem, velocity, gravitational force, Newton's law, meta heuristic, combinatorial optimization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1086241

References:

[1] Aickelin, U., An indirect genetic algorithm for set covering problems, Journal of the Operational Research Society 53, 1118-1126,2002.
[2] Almiana M, Pastor JT, An adaptation of SH heuristic to the location set covering problem, European Journal of Operational Research; 100(3):586-93,1997
[3] Barry Lynn Webster, Solving combinatorial Optimization Problems using a newalgorithm based on gravitational attraction, Ph.D., thesis, Melbourne, Florida Institute of Technology, May 2004.
[4] Beasley J.E, An algorithm for set covering problems, European Journal of Operational Research 31 85-93,1990
[5] Beasley J.E, A Lagrangean heuristic for set covering problems, Naval Research Logistics ; 37(1):151-64,1990.
[6] Beasley J.E., Jornsten. K, Enhancing an algorithm for set covering problems, European Journal of Operational Research 58, 293-300,1992.
[7] Beasley J.E, Chu PC, A genetic algorithm for the set covering problem, EuropeanJournal of Operational Research; 94(2):392-404,1996.
[8] Brusco M.J.,.Jacobs L.W,.Thomson G.M, A morphing procedure to supplement a simulated annealing heuristic for cost-and-coverage-correlated set-covering problem, Annals of Operations Research 86, 611-627,1999.
[9] Caprara A. , Fischetti M. Toth ,P. ,D.vigo and Guida P.L., Algorithms for railway crew management ,Mathematical programming 79 , 125 - 141,1997.
[10] Caprara A, Fischetti M, Toth P, A heuristic method for the set covering problem, Operational Research; 47(5):730-743,1999.
[11] Ceria S., Nobili P., Sassano A, A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programming 81, 215- 228,1998.
[12] Chvatal. V, A greedy heuristic for the set-covering problem,Mathematics of Operations Research 4, 233-235,1979.
[13] Feo, T., Resende, M.G.C, A probabilistic heuristic for a computationally difficult set covering problem. Operations ResearchLetters 8, 67-71,1989.
[14] Fisher M.L., Kedia P, Optimal solutions of set covering/partitioning problems using dual heuristics, Management Science 36, 674-688,1990.
[15] Garey M.R. and. Johnson D.S, Computers and Intractability: A Guide to the theory of NP-completeness , W.H.Freeman ,San Francisco,1979.
[16] Grossman T,Wool A, Computational experience with approximation algorithms for the set covering problem. European Journal of Operational Research; 101(1):81-92,1997.
[17] Guanghui Lan, Gail W. DePuy, Gary E. Whitehouse, An effective and simple heuristic for the set covering problem, European Journal of Operational Research 176, 1387-1403,2007.
[18] Haouari, M., Chaouachi, J.S., A probabilistic greedy search algorithm for combinatorial optimization with application to the setcovering problem, Journal of the Operational Research Society 53, 792-799,2002.
[19] Harche E and Thompson G.L., The column subtraction algorithm: An exact method for solving weighted setcovering, packing and partitioning problems, Computers and Operations Research 21, 689-705,1994.
[20] D. Holliday, R. Resnick, J. Walker, Fundamentals of physics, John Wiley and Sons, 1993.
[21] Jacobs L.W. and Brusco M.J.,A simulated annealing based heuristic for the set-covering problem, Working paper, Operations Management and Information Systems Department, Northern Illinois University, Dekalb, IL, 1993.
[22] Jacobs, L., Brusco, M., Note: A local-search heuristic for large setcovering problems, Naval Research Logistics 42, 1129-1140.22,1995.
[23] I.R. Kenyon, General Relativity, Oxford University Press, 1990.
[24] Lessing L, Dumitrescu I, Sttzle T, A comparison between ACO algorithms for the set covering problem, Lecture Notes in Computer Science; 3172;1-12,2004.
[25] Lopes FB, Lorena LA, Surrogate heuristic for set covering problems, European Journal of Operational Research; 79(1):138-150,1994.
[26] R. Mansouri, F. Nasseri, M. Khorrami, Effective time variation of G in a model universe with variable space dimension, Physics Letters 259,194- 200,1999.
[27] Ohlsson, M., Peterson, C., Soderberg, B., An efficient mean field approach to the set covering problem, European Journal of Operational Research 133, 583-595,2001.
[28] E. Rashedi, Gravitational Search Algorithm, M.Sc. Thesis, Shahid Bahonar University of Kerman, Kerman, Iran, 2007.
[29] B. Schutz, Gravity from the Ground Up, Cambridge University Press, 2003.
[30] Sears,Francis W., Mark W.Zemansky and Hugh D. Young, University Physics, 7th ed.Reading,MA.Addison - Wesley,1987.
[31] Solar M, Parada V, Urrutia R., A parallel genetic algorithm to solve the set-covering problem, Computer Operational Research; 29(9):1221- 35,2002.
[32] Vasko, F.J., Wilson, G.R., An efficient heuristic for large set covering problems, Naval Research Logistics Quarterly 31, 163-171,1984.
[33] Voudouris,chris and Edward Tsang, Guided Local Search, Technical Report,CSM-247,Department of Computer Science,University of Essex, UK,1995.
[34] Yagiura M, Kishida M, Ibaraki T., A 3-flip neighborhood local search for the set covering problem, Technical Report 2004-001. Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University,2004