An effective and simple heuristic for the set covering problem
Abbreviated Journal Title
Eur. J. Oper. Res.
Keywords
combinatorial optimization; set covering; Meta-RaPS; GENETIC ALGORITHM; META-RAPS; Management; Operations Research & Management Science
Abstract
This paper investigates the development of an effective heuristic to solve the set covering problem (SCP) by applying the meta-heuristic Meta-RaPS (Meta-heuristic for Randomized Priority Search). In Meta-RaPS, a feasible solution is generated by introducing random factors into a construction method. Then the feasible solutions can be improved by an improvement heuristic. In addition to applying the basic Meta-RaPS, the heuristic developed herein integrates the elements of randomizing the selection of priority rules, penalizing the worst columns when the searching space is highly condensed, and defining the core problem to speedup the algorithm. This heuristic has been tested on 80 SCP instances from the OR-Library. The sizes of the problems are up to 1000 rows x 10,000 columns for non-unicost SCP, and 28,160 rows x 11.264 columns for the unicost SCP. This heuristic is only one of two known SCP heuristics to find all optimal/best known solutions for those non-unicost instances. In addition, this heuristic is the best for unicost problems among the heuristics in terms of solution quality. Furthermore, evolving from a simple greedy heuristic, it is simple and easy to code. This heuristic enriches the options of practitioners in the optimization area. (c) 2005 Elsevier B.V. All rights reserved.
Journal Title
European Journal of Operational Research
Volume
176
Issue/Number
3
Publication Date
1-1-2007
Document Type
Article
Language
English
First Page
1387
Last Page
1403
WOS Identifier
ISSN
0377-2217
Recommended Citation
"An effective and simple heuristic for the set covering problem" (2007). Faculty Bibliography 2000s. 7331.
https://stars.library.ucf.edu/facultybib2000/7331
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu