A GRASP-based scheme for the set covering problem

Research output: Contribution to journalArticlepeer-review

Abstract

In this work we present a greedy randomized adaptive search procedure (GRASP)-based strategy for the set covering problem. The goal of this problem is to find a subset of columns from a zero-one matrix in order to cover all the rows with the minimal possible cost. The GRASP is a technique that through a sequential and finite number of steps constructs a solution using a set of simple randomized rules. Additionally, we also propose an iterated local search and reward/penalty procedures in order to improve the solutions found by the GRASP. Our approach has been tested using the well-known 65 non-unicost SCP benchmark instances from OR-library showing promising results.

Original languageEnglish
JournalOperational Research
DOIs
StateAccepted/In press - 2019
Externally publishedYes

Keywords

  • GRASP
  • Local search
  • Metaheuristics
  • Set covering problem

Fingerprint Dive into the research topics of 'A GRASP-based scheme for the set covering problem'. Together they form a unique fingerprint.

Cite this