Two difficulties arise when solving the set covering problem (SCP) with metaheuristic approaches: solution infeasibility and set redundancy. In this paper, we first present a review and analysis of the heuristic approaches that have been used in the literature to address these difficulties. We then present a new formulation that can be used to solve the SCP as an unconstrained optimization problem and that eliminates the need to address the infeasibility and set redundancy issues. We show that all local optimums with respect to the new formulation and a 1-flip neighbourhood structure are feasible and free of redundant sets. In addition, we adapt an existing greedy heuristic for the SCP to the new formulation and compare the adapted heuristic to the original heuristic using 88 known test problems for the SCP. Computational results show that the adapted heuristic finds better results than the original heuristic on most of the test problems in shorter computation times. 1. Introduction The set covering problem (SCP) is a popular optimization problem that has been applied to a wide range of industrial applications, including scheduling, manufacturing, service planning, and location problems [1–4]. The SCP is NP hard in the strong sense [5]. The mathematical formulation of the SCP is as follows. Let be a universe of elements, and let be a collection of subsets , where . Each set covers at least one element of and has an associated cost . The objective is to find a subcollection of sets that covers all of the elements in at a minimal cost. The mathematical programming model of the SCP is usually formulated as follows. (i)Let be a zero-one matrix where if element is covered by set and otherwise. (ii)Let where if set (with cost ) is part of the solution and otherwise. Minimize subject to The objective function (1) drives the search toward solutions at minimal cost. Constraint (2) (full coverage constraint) imposes the requirement that all the elements of the universe must be covered. If constraint (2) is not satisfied, the solution is infeasible. If constraint (2) is satisfied and the objective function is minimized, the solution will cover all of the elements at the minimal cost (optimal solution). If constraint (2) is relaxed, the objective function will drive the search toward an empty solution because the empty solution has the lowest cost (0). These observations show that the objective function and the full coverage constraint of the SCP guide the search in two opposite directions. When solving the model with metaheuristic algorithms, two issues arise:
References
[1]
A. Caprara, M. Fischetti, and P. Toth, “Heuristic method for the set covering problem,” Operations Research, vol. 47, no. 5, pp. 730–743, 1999.
[2]
G. Lan, G. W. DePuy, and G. E. Whitehouse, “An effective and simple heuristic for the set covering problem,” European Journal of Operational Research, vol. 176, no. 3, pp. 1387–1403, 2007.
[3]
E. Balas, Class of Location, Distribution and Scheduling Problems: Modeling and Solution Methods, Carnegie Mellon University. Design Research Center, New York, NY, USA, 1983.
[4]
S. Ceria, “Set covering problem,” in Annotated Bibliographies in Combinatorial Optimization, 1997.
[5]
M. Garey and D. Johnson, Computers and Intractability. A Guide To the Theory of NP-Completeness, W. H. Freeman, Oxford, UK, 1979.
[6]
L. Lessing, I. Dumitrescu, and T. Stutzle, “A comparison between acoalgorithms for the set covering problem,” Ant Colony Optimization and Swarm Intelligence, pp. 105–122, 2004.
[7]
M. Rahoual, R. Hadji, and V. Bachelet, “Parallel ant system for the set covering problem,” in Ant Algorithmspages, pp. 249–297, 2002.
[8]
Z. Ren, Z. Feng, L. Ke, and H. Chang, “A fast and efficient ant colony optimization approach for the set covering problem,” in Proceedings of the IEEE Congress on Evolutionary Computation (CEC '08), (IEEE World Congress on Computational Intelligence), pp. 1839–1844, IEEE, June 2008.
[9]
Z. G. Ren, Z. R. Feng, L. J. Ke, and Z. J. Zhang, “New ideas for applying ant colony optimization to the set covering problem,” Computers and Industrial Engineering, vol. 58, no. 4, pp. 774–784, 2010.
[10]
B. Crawford and C. Castro, “Integrating lookahead and post processing procedures with aco for solving set partitioning and covering problems,” in proceedings of the 8th International Conference on Artificial Intelligence and Soft Computing (ICAISC '06), pp. 1082–1090, 2006.
[11]
G. DePuy, G. Whitehouse, and R. Moraga, “Using the meta-raps approach to solve combinatorial problems,” in Proceedings of the 2002 Industrial Engineering Research Conference, vol. 19, p. 21, Citeseer, May 2002.
[12]
T. A. Feo and M. G. C. Resende, “Greedy randomized adaptive search procedures,” Journal of Global Optimization, vol. 6, no. 2, pp. 109–133, 1995.
[13]
J. E. Beasley and P. C. Chu, “A genetic algorithm for the set covering problem,” European Journal of Operational Research, vol. 94, no. 2, pp. 392–404, 1996.
[14]
M. Solar, V. Parada, and R. Urrutia, “A parallel genetic algorithm to solve the set-covering problem,” Computers and Operations Research, vol. 29, no. 9, pp. 1221–1235, 2002.
[15]
D. Orvosh and L. Davis, “Using a genetic algorithm to optimize problems with feasibility constraints,” in Proceedings of the 1st IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, pp. 548–553, IEEE, June 1994.
[16]
T. B？ck, M. Schütz, and S. Khuri, “A comparative study of a penalty function, a repair heuristic, and stochastic operators with the set-covering problem,” in Artificial Evolution, pp. 320–332, Springer, New York, NY, USA, 1996.
[17]
K. S. Al-Sultan, M. F. Hussain, and J. S. Nizami, “A genetic algorithm for the set covering problem,” Journal of the Operational Research Society, vol. 47, no. 5, pp. 702–709, 1996.
[18]
R. L. Wang and K. Okazaki, “An improved genetic algorithm with conditional genetic operators and its application to set-covering problem,” Soft Computing, vol. 11, no. 7, pp. 687–694, 2007.
[19]
N. Musliu, “Local search algorithm for unicost set covering problem,” Advances in Applied Artificial Intelligence, vol. 4031, pp. 302–311, 2006.
[20]
M. Yagiura, M. Kishida, and T. Ibaraki, “A 3-flip neighborhood local search for the set covering problem,” European Journal of Operational Research, vol. 172, no. 2, pp. 472–499, 2006.
[21]
E. Balas and M. C. Carrera, “A dynamic subgradient-based branch-and-bound procedure for set covering,” Operations Research, vol. 44, no. 6, pp. 875–890, 1996.
[22]
J. E. Beasley, “Lagrangian heuristic for set-covering problems,” Naval Research Logistics, vol. 37, no. 1, pp. 151–164, 1990.
[23]
G. Kinney and J. Barnes, “A group theoretic tabu search algorithm for set covering problems,” Working Paper, 2004, http://www.researchgate.net/publication/228734774_A_group_theoretic_tabu_search_algorithm_for_set_covering_problems.
[24]
G. W. Kinney, J. W. Barnes, and B. W. Colletti, “A reactive tabu search algorithm with variable clustering for the Unicost set covering problem,” International Journal of Operational Research, vol. 2, no. 2, pp. 156–172, 2007.
[25]
J. Bautista and J. Pereira, “A GRASP algorithm to solve the unicost set covering problem,” Computers and Operations Research, vol. 34, no. 10, pp. 3162–3173, 2007.
[26]
M. Caserta, “Tabu search-based metaheuristic algorithm for large-scale set covering problems,” Metaheuristics, vol. 39, pp. 43–63, 2007.
[27]
M. L. Fisher, “The lagrangian relaxation method for solving integer programming problems,” Management Science, vol. 27, no. 1, pp. 1–18, 1981.
[28]
M. Held, P. Wolfe, and H. P. Crowder, “Validation of subgradient optimization,” Math Program, vol. 6, no. 1, pp. 62–88, 1974.
[29]
V. Chvatal, “A greedy heuristic for the set-covering problem,” Mathematics of Operations Research, vol. 4, no. 3, pp. 233–235, 1979.
[30]
J. Beasley, “OR-library: distributing test problems by electronic mail,” Journal of the Operational Research Society, vol. 41, no. 11, pp. 1069–1072, 1990.
[31]
B. Yelbay, S. Birbil, and K. Bulbul, “The set covering problem revisited: an empirical study of the value of dual information,” Optimization Online, 2012.
