Abstract
The non-unicost Set Covering Problem is a well-known NP-hard problem with many practical applications. In this work, a new approach based on Binary Firefly Algorithm is proposed to solve this problem. The Firefly Algorithm has attracted much attention and has been applied to many optimization problems. Here, we demonstrate that is also able to produce very competitive results solving the portfolio of set covering problems from the OR-Library.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Housos, E., Elmoth, T.: Automatic optimization of subproblems in scheduling airlines crews. Interfaces 27(5), 68–77 (1997)
Vasko, F.J., Wilson, G.R.: Using a facility location algorithm to solve large set covering problems. Oper. Res. Lett. 3(2), 85–90 (1984)
Vasko, F.J., Wolf, F.E.: Optimal selection of ingot sizes via set covering. Oper. Res. 35(3), 346–353 (1987)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co, New York (1990)
Balas, E., Carrera, M.C.: A dynamic subgradient-based branch-and-bound procedure for set covering. Oper. Res. 44(6), 875–890 (1996)
Fisher, M.L., Kedia, P.: Optimal solution of set covering/partitioning problems using dual heuristics. Manage. Sci. 36(6), 674–688 (1990)
Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979)
Lan, G., DePuy, G.W.: On the effectiveness of incorporating randomness and memory into a multi-start metaheuristic with application to the set covering problem. Comput. Ind. Eng. 51(3), 362–374 (2006)
Ceria, S., Nobili, P., Sassano, A.: A Lagrangian-based heuristic for large-scale set covering problems. Math. Program. 81(2), 215–228 (1998)
Caprara, A., Fischetti, M., Toth, P.: A heuristic method for the set covering problem. Oper. Res. 47(5), 730–743 (1999)
Beasley, J.E., Chu, P.C.: A genetic algorithm for the set covering problem. Eur. J. Oper. Res. 94(2), 392–404 (1996)
Brusco, M.J., Jacobs, L.W., Thompson, G.M.: A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems. Ann. Oper. Res. 86, 611–627 (1999)
Caserta, M.: Tabu search-based metaheuristic algorithm for large-scale set covering problems. In: Doerner, K., Gendreau, M., Greistorfer, P., Gutjahr, W., Hartl, R., Reimann, M. (eds.) Metaheuristics. Vol. 39 of Operations Research/Computer Science Interfaces Series, pp. 43–63. Springer, US (2007)
Crawford, B., Lagos, C., Castro, C., Paredes, F.: A evolutionary approach to solve set covering. In: Cardoso, J., Cordeiro, J., Filipe, J. (eds.) In: Proceedings of the 9th International Conference on Enterprise Information Systems (ICEIS '07), Vol. AIDSS, pp. 356-363. Funchal, Portugal. 12-16 June 2007
Ren, Z.G., Feng, Z.R., Ke, L.J., Zhang, Z.J.: New ideas for applying ant colony optimization to the set covering problem. Comput. Ind. Eng. 58(4), 774–784 (2010)
Naji-Azimi, Z., Toth, P., Galli, L.: An electromagnetism metaheuristic for the unicost set covering problem. Eur. J. Oper. Res. 205(2), 290–300 (2010)
Balachandar, S.R., Kannan, K.: A meta-heuristic algorithm for set covering problem based on gravity. J. Comput. Math. Sci. 4, 223–228 (2010)
Crawford, B., Soto, R., Monfroy, E.: Cultural algorithms for the set covering problem. In: Tan, Y., Shi, Y., Mo, H. (eds.) ICSI (2). Vol. 7929 of Lecture Notes in Computer Science, pp. 27–34. Springer, Berlin (2013)
Caprara, A., Toth, P., Fischetti, M.: Algorithms for the set covering problem. Ann. Oper. Res. 98, 353–371 (2000)
Yang, X.S.: Nature-Inspired Metaheuristic Algorithms. Luniver Press, UK (2008)
Yang, X.S.: Firefly algorithms for multimodal optimisation, In: Proceedings of the 5th International Conference on Stochastic Algorithms: Foundations and Applications. SAGA’09, pp. 169–178. Springer, Berlin (2009)
Fister, I., Fister Jr, I., Yang, X.S., Brest, J.: A comprehensive review of firefly algorithms. Swarm Evol. Comput. 13, 34–46 (2013)
Yang, X.S., He, X.: Firefly Algorithm: Recent Advances and Applications. The Computing Research Repository, abs/1308.3898 (2013)
Chandrasekaran, K., Sishaj, P.S., Padhy, N.P.: Binary real coded firefly algorithm for solving unit commitment problem. Inf. Sci. 249, 67–84 (2013)
Beasley, J.E.: A Lagrangian heuristic for set covering problems. Naval Res. Logistics 37(1), 151–164 (1990)
Crawford, B., Soto, R., Monfroy, E., Palma, W., Castro, C., Paredes, P.: Parameter tuning of a choice-function based hyperheuristic using particle swarm optimization. Expert Syst. Appl. 40(5), 1690–1695 (2013)
Soto, R., Crawford, B., Monfroy, E., Bustos, V.: Using autonomous search for generating good enumeration strategy blends in constraint programming. In: Proceedings of the 12th International Conference on Computational Science and Its Applications (ICCSA). Vol. 7335 of LNCS, pp. 607–617. Springer (2012)
Crawford, B., Soto R., Montecinos M., Castro C., Monfroy, E.: A framework for autonomous search in the eclipse solver. In: Proceedings of the 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE). Vol. 6703 of LNCS, pp. 79–84. Springer (2011)
Crawford, B., Soto R., Castro C., Monfroy, E.: Extensible CP-based autonomous search. In: Proceedings of HCI International. Vol. 173 of CCIS, pp. 561–565. Springer (2011)
Acknowledgements
The author B. Crawford is supported by Grant CONICYT/FONDECYT/REGU- LAR/1140897. The author R. Soto is supported by Grant CONICYT/FON- DECYT/INICIACION/11130459. The author F. Paredes is supported by Grant CONICYT/FONDECYT/REGULAR/1130455.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Crawford, B., Soto, R., Olivares-Suárez, M., Paredes, F. (2014). A Binary Firefly Algorithm for the Set Covering Problem. In: Silhavy, R., Senkerik, R., Oplatkova, Z., Silhavy, P., Prokopova, Z. (eds) Modern Trends and Techniques in Computer Science. Advances in Intelligent Systems and Computing, vol 285. Springer, Cham. https://doi.org/10.1007/978-3-319-06740-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-06740-7_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06739-1
Online ISBN: 978-3-319-06740-7
eBook Packages: EngineeringEngineering (R0)