%0 Journal Article
%T A New Formulation of the Set Covering Problem for Metaheuristic Approaches
%A Nehme Bilal
%A Philippe Galinier
%A Francois Guibault
%J ISRN Operations Research
%D 2013
%R 10.1155/2013/203032
%X 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¨C4]. 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:
%U http://www.hindawi.com/journals/isrn.operations.research/2013/203032/