Title

An Effective And Simple Heuristic For The Set Covering Problem

Keywords

Combinatorial optimization; Meta-RaPS; Set covering

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 × 10,000 columns for non-unicost SCP, and 28,160 rows × 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. © 2005 Elsevier B.V. All rights reserved.

Publication Date

2-1-2007

Publication Title

European Journal of Operational Research

Volume

176

Issue

3

Number of Pages

1387-1403

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.ejor.2005.09.028

Socpus ID

33750018061 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/33750018061

This document is currently not available here.

Share

COinS