Comparing Heuristic Efficiencies in Solving the Set Cover Problem
DOI:
https://doi.org/10.26821/IJSHRE.10.7.2022.100509Keywords:
Combinatorial Optimization Problem, Particle Swarm Optimization, Algorithm, Combinatorics, Set Cover ProblemAbstract
Most combinatorial optimization problems can be solved using various heuristic approaches, but it is often a challenge to determine which is the best option out of the vast choices of heuristics. One such heuristic is the Particle Swarm Optimization (PSO), which is compared to the greedy algorithm in order to determine which is more efficient for solving the Set Cover problem. In order to compare the efficiency of the two algorithms, the runtime and solution of each of the algorithms will be used to find the runtime to solution ratio. Unlike the greedy algorithm, which has no adjustable variables, the PSO algorithm consists of three adjustable variables--maximum generation, maximum fitness, and particle numbers-- that are to be increased in various magnitudes while keeping the ratio between the three variables constant. The code is then run ten times for each magnitude, and the resulting runtime and solution are recorded and averaged. From the recorded data, the time to solution ratio of the two algorithms suggest that the PSO algorithm is more efficient than the greedy algorithm. Although the solution for the PSO was inconsistent for lower magnitudes of variables, it was optimized as the magnitude increased. The efficiency of the PSO algorithm indicates potential for the algorithm to be applied in other combinatorial optimization problems.
References
Gao, X., Du, H., & Han, M. (2017). Approximation Algorithms for the Generalized Stacker Crane Problem. In Combinatorial Optimization and Applications 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I (pp. 111–112). essay, Cham: Springer International Publishing.
Uppman, H. (2015). On Some Combinatorial Optimization Problems. Algorithms and Complexity. https://www.diva-portal.org/smash/get/diva2:806491/FULLTEXT01.pdf. Accessed 10 August 2020
Schrijver, A, Henderson, S. G., & Nelson, B. L. (2005). On the History of Combinatorial Optimization (Till 1960). In Handbooks in Operations Research and Management Science (pp. 1–68). essay, Amsterdam: Elsevier.
Cook, S. (2000). The P Versus NP Problem. Clay Mathematics Institute. https://www.claymath.org/. Accessed 19 August 2020
Landman, N., Moore, K., & Williams, C. (2016). P versus NP. Brilliant Math & Science Wiki. https://brilliant.org/wiki/p-versus-np/. Accessed 19 August 2020
Pavlus, J. (2020, April 2). What Does 'P vs. NP' Mean for the Rest of Us? MIT Technology Review. MIT Technology Review. https://www.technologyreview.com/2010/08/19/262224/what-does-p-vs-np-mean-for-the-rest-of-us/. Accessed 25 August 2020
Hardesty, L. (2009, October 29). Explained: P vs. NP. MIT News | Massachusetts Institute of Technology. https://news.mit.edu/2009/explainer-pnp. Accessed 25 August 2020
Stern, T. (2006). What is the Set Cover Problem (Chapter 2.1, 12). Massachusetts Institute of Technology. https://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf. Accessed 10 August 2020
Shabir, S., & Singla, R. (2016). A Comparative Study of Genetic Algorithm and the Particle Swarm Optimization. International Research Publication House. https://www.ripublication.com/irph/ijee16/ijeev9n2_06.pdf. Accessed 19 August 2020
Chvatal, Vasek. "A greedy heuristic for the set-covering problem." Mathematics of operations research 4.3 (1979): 233-235.
Karp, Richard M. "Reducibility among combinatorial problems." Complexity of computer computations. Springer, Boston, MA, 1972. 85-103.
Caprara, Alberto, Matteo Fischetti, and Paolo Toth. "A heuristic method for the set covering problem." Operations research 47.5 (1999): 730-743.
DeVore, Ronald A., and Vladimir N. Temlyakov. "Some remarks on greedy algorithms." Advances in computational Mathematics 5.1 (1996): 173-187.
Vazirani, Vijay V. Approximation algorithms. Springer Science & Business Media, 2013.
Grossman, Tal, and Avishai Wool. "Computational experience with approximation algorithms for the set covering problem." European Journal of Operational Research 101.1 (1997): 81-92.
Holland, John H. "Genetic algorithms." Scientific american 267.1 (1992): 66-73.
Kennedy, J. and Eberhart, R., 1995, November. Particle swarm optimization. In Proceedings of ICNN'95-International Conference on Neural Networks (Vol. 4, pp. 1942-1948). IEEE.
Ren, J. and Yang, S., 2011, October. A particle swarm optimization algorithm with momentum factor. In 2011 Fourth International Symposium on Computational Intelligence and Design (Vol. 1, pp. 19-21). IEEE.
Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization", IEEE Transactions on Evolutionary Computation 1, 67.
Eberhart R,Shi Y.Comparing inertia weights and constriction factors in particle swarm optimization[C].IEEE Congress on Evolutionary Computation,2000:84-88
JI Zhen, LIAO Hui-lian and WU Qing-hua. Particle Swarm Optimization and Application [M]. BeiJing: The Science Publishing Company, 2009
B. Goethals. Frequent itemset mining dataset repository. http://fimi.cs.helsinki.fi/data/. Accessed 13 November 2020
Cormode, G., Karloff, H., & Wirth, A. (2010, October). Set Cover Algorithms For Very Large Datasets. http://www.dimacs.rutgers.edu/~graham/pubs/papers/ckw.pdf. Accessed 2 January 2021
Bowling Green University. Set Covering Model - Class Examples. https://www.coursehero.com/file/31649465/Set-Covering-handout-1docx/. Accessed 10 November 2020
