A New Formulation of the Set Covering Problem for Metaheuristic Approaches. (23rd April 2013)

• Record Type: Journal Article
• Authors: Bilal, Nehme; Galinier, Philippe; Guibault, Francois
• Other Names: Buzna L. Academic Editor.; Ekel P. Academic Editor.; Mohan C. Academic Editor.; Wang M. Academic Editor.
• Is Part Of: ISRN operations research. Volume 2013(2013)
• Publication Date: 2013-04-23
• Subjects: Operations research -- Periodicals; Operations research; Electronic journals; Periodicals; 003
• DOI: 10.1155/2013/203032
• Languages: English
• ISSNs: 2314-6397

Abstract

Abstract : 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.