**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**31097

##### Solving the Set Covering Problem Using the Binary Cat Swarm Optimization Metaheuristic

**Authors:**
Broderick Crawford,
Ricardo Soto,
Natalia Berrios,
Eduardo Olguin

**Abstract:**

**Keywords:**
metaheuristic,
binary cat swarm optimization,
binarization methods,
set covering problem

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

**References:**

[1] U. Aickelin. An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society, pages 1118–1126, 2002.

[2] A. I. Ali and H. Thiagarajan. A network relaxation based enumeration algorithm for set partitioning. European Journal of Operational Research, 38(1):76–85, 1989.

[3] F. Amini and P. Ghaderi. Hybridization of harmony search and ant colony optimization for optimal locating of structural dampers. Applied Soft Computing, pages 2272–2280, 2013.

[4] M. L. Balinski and R. E. Quandt. On an integer program for a delivery problem. Operations Research, 12(2):300–304, 1964.

[5] J. Beasley. A lagrangian heuristic for set covering problems. Naval Research Logistics, 37:151–164, 1990.

[6] J. Beasley and K. Jornsten. Enhancing an algorithm for set covering problems. European Journal of Operational Research, 58(2):293–300, April 1992.

[7] M. Bellmore and H. D. Ratliff. Optimal defense of multi-commodity networks. Management Science, 18(4-part-i):B174–B185, 1971.

[8] M. A. Breuer. Simplification of the covering problem with application to boolean expressions. Journal of the Association for Computing Machinery, 17(1):166–181, Jan. 1970.

[9] A. Caprara, M. Fischetti, and P. Toth. Algorithms for the set covering problem. Annals of Operations Research, 98:353–371, 2000.

[10] N. Christofides. Zero-one programming using non-binary tree-search. Computer Journal, 14(4):418–421, 1971.

[11] S. Chu and P. Tsai. Computational intelligence based on the behavior of cats. International Journal of Innovative Computing, Information and Control, pages 163 – 173, 2007.

[12] S. Chu, P. Tsai, and J. Pan. Cat swarm optimization. In Trends in Artificial Intelligence, pages 854–858. Springer-Verlag, Berlin, Heidelberg, 2006.

[13] B. Crawford, R. Soto, N. Berrios, F. Johnson, F. Paredes, C. Castro, and E. Norero. A binary cat swarm optimization algorithm for the non-unicost set covering problem. Mathematical Problems in Engineering, 2015(Article ID 578541):1–8, 2015.

[14] B. Crawford, R. Soto, R. Cuesta, and F. Paredes. Application of the artificial bee colony algorithm for solving the set covering problem. The Scientific World Journal, 2014(Article ID 189164):1–8, 2014.

[15] B. Crawford, R. Soto, and E. Monfroy. Cultural algorithms for the set covering problem. In Y. Tan, Y. Shi, and H. Mo, editors, Advances in Swarm Intelligence, 4th International Conference, volume 7929 of Lecture Notes in Computer Science, pages 27–34. Springer, Harbin, China, 2013.

[16] B. Crawford, R. Soto, E. Monfroy, W. Palma, C. Castro, and F. Paredes. Parameter tuning of a choice-a function based hyperheuristic using particle swarm optimization. Expert Systems with Applications, pages 1690–1695, 2013.

[17] B. Crawford, R. Soto, M. Olivares-Su´arez, W. Palma, F. Paredes, E. Olguin, and E. Norero. A binary coded firefly algorithm that solves the set covering problem. volume 17, pages 252–264, 2014.

[18] B. Crawford, R. Soto, M. Olivares-Su´arez, and F. Paredes. A binary firefly algorithm for the set covering problem. In 3rd Computer Science On-line Conference 2014, Modern Trends and Techniques in Computer Science, volume 285, pages 65–73. Springer, 2014.

[19] B. Crawford, R. Soto, C. Pe˜na, W. Palma, F. Johnson, and F. Paredes. Solving the set covering problem with a shuffled frog leaping algorithm. In N. T. Nguyen, B. Trawinski, and R. Kosala, editors, Intelligent Information and Database Systems - 7th Asian Conference, volume 9012 of LNCS, pages 41–50, Bali, Indonesia, 2015. Springer.

[20] B. Crawford, R. Soto, M. Riquelme-Leiva, C. Pena, C. Torres-Rojas, F. Johnson, and F. Paredes. Set covering problem solved by new binary firefly algorithm. In 10th Iberian Conference on Information Systems and Technologies, pages 1–4. 2015.

[21] R. H. Day. Letter to the editoron optimal extracting from a multiple file data storage system: An application of integer programming. Operations Research, 13(3):482–494, 1965.

[22] M. L. Fisher and M. B. Rosenwein. An interactive optimization system for bulk-cargo ship scheduling. Naval Research Logistics, 36(1):27–42, 1989.

[23] B. A. Freeman and J. V. Jucker. The line balancing problem. Journal of Industrial Engineering, 18:361–364, 1967.

[24] R. S. Garfinkel and G. L. Nemhauser. Optimal political districting by implicit enumeration techniques. Management Science, 16(8):B495–B508, 1970.

[25] D. Goldberg. Real-coded genetic algorithms, virtual alphabets, and blocking. Complex Systems, pages 139–167, 1990.

[26] D. Gouwanda and S. Ponnambalam. Evolutionary search techniques to solve set covering problems. World Academy of Science, Engineering and Technology, 39:20–25, 2008.

[27] E. Housos and T. Elmroth. Automatic optimization of subproblems in scheduling airline crews. Interfaces, 27(5):68–77, 1997.

[28] L. Lessing, I. Dumitrescu, and T. Stutzle. A comparison between aco algorithms for the set covering problem. In Ant Colony Optimization and Swarm Intelligence, pages 1–12. 2004.

[29] G. Panda, P. Pradhan, and B. Majhi. Iir system identification using cat swarm optimization. Expert Systems with Applications, 38:12671–12683, 2011.

[30] Z. Ren, Z. Feng, L. Ke, and Z. Zhang. New ideas for applying ant colony optimization to the set covering problem. Computers & Industrial Engineering, pages 774 – 784, 2010.

[31] C. C. Ribeiro, M. Minoux, and M. C. Penna. An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment. European Journal of Operational Research, 41(2):232–239, 1989.

[32] Y. Sharafi, M. Khanesar, and M. Teshnehlab. Discrete binary cat swarm optimization algorithm. Computer, Control and Communication, pages 1–6, 2013.

[33] P. Tsai, J. Pan, S. Chen, and B. Liao. Enhanced parallel cat swarm optimization based on the taguchi method. Expert Systems with Applications, 39:6309–6319, 2012.

[34] F. J. Vasko, F. E. Wolf, and K. L. Stott. Optimal selection of ingot sizes via set covering. Operations Research, 35(3):346–353, June 1987.

[35] W. Walker. Using the set-covering problem to assign fire companies to fire houses. Operations Research, 22:275–277, 1974.