A GRASP-based scheme for the set covering problem

Victor Reyes, Ignacio Araya

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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
Pages (from-to)2391-2408
Number of pages18
JournalOperational Research
Issue number4
StatePublished - Dec 2021


  • Local search
  • Metaheuristics
  • Set covering problem


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

Cite this