Abstract
The non-unicost set covering problem is a classical optimization benchmark that belongs to the Karp’s 21 NP-complete problems. In this paper, we present a new approach based on cuckoo search for solving such problem. Cuckoo search is a modern nature-inspired metaheuristic that has attracted much attention due to its rapid convergence and easy implementation. We illustrate interesting experimental results where the proposed cuckoo search algorithm reaches several global optimums for the non-unicost instances from the OR-Library.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Balas, E., Carrera, M.C.: A dynamic subgradient-based branch-and-bound procedure for set covering. Oper. Res. 44(6), 875–890 (1996)
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)
Caprara, A., Fischetti, M., Toth, P.: A heuristic method for the set covering problem. Oper. Res. 47(5), 730–743 (1999)
Caprara, A., Toth, P., Fischetti, M.: Algorithms for the set covering problem. Ann. Oper. Res. 98, 353–371 (2000)
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. Operations Research/Computer Science Interfaces Series, vol. 39, pp. 43–63. Springer, US (2007)
Ceria, S., Nobili, P., Sassano, A.: A Lagrangian-based heuristic for large-scale set covering problems. Math. Program. 81(2), 215–228 (1998)
Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979)
Crawford, B., Castro, C., Monfroy, E., Soto, R., Palma, W., Paredes, F.: Dynamic Selection of Enumeration Strategies for Solving Constraint Satisfaction Problems. Romanian Journal of Information Science and Technology 15(2), 106–128 (2013)
Fisher, M.L., Kedia, P.: Optimal solution of set covering/partitioning problems using dual heuristics. Management Science 36(6), 674–688 (1990)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)
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)
Vasko, F.J., Wolf, F.E.: Optimal selection of ingot sizes via set covering. Oper. Res. 35(3), 346–353 (1987)
Yang, X.-S., Deb, S.: Cuckoo search via Lévy Flights. In: Proc. of World Congress on Nature & Biologically Inspired Computing (NaBIC 2009), pp. 210–214. IEEE Publications, USA (December 2009)
Yang, X.S.: Bat algorithm and cuckoo search: a tutorial. In: Yang, X.S. (ed.) Artificial Intelligence, Evolutionary Computing and Metaheuristics. SCI, vol. 427, pp. 421–434. Springer, Heidelberg (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Soto, R., Crawford, B., Olivares, R., Barraza, J., Johnson, F., Paredes, F. (2015). A Binary Cuckoo Search Algorithm for Solving the Set Covering Problem. In: Ferrández Vicente, J., Álvarez-Sánchez, J., de la Paz López, F., Toledo-Moreo, F., Adeli, H. (eds) Bioinspired Computation in Artificial Systems. IWINAC 2015. Lecture Notes in Computer Science(), vol 9108. Springer, Cham. https://doi.org/10.1007/978-3-319-18833-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-18833-1_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18832-4
Online ISBN: 978-3-319-18833-1
eBook Packages: Computer ScienceComputer Science (R0)