Title

An effective and simple heuristic for the set covering problem

Authors

Authors

G. H. Lan; G. W. DePuy;G. E. Whitehouse

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

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

WOS:000242102800007

ISSN

0377-2217

Share

COinS