A GRASP-based scheme for the set covering problem

Victor Reyes () and Ignacio Araya ()
Additional contact information
Victor Reyes: Pontificia Universidad Católica de Valparaíso
Ignacio Araya: Pontificia Universidad Católica de Valparaíso

Operational Research, 2021, vol. 21, issue 4, No 8, 2408 pages

Abstract: 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.

Keywords: GRASP; Set covering problem; Local search; Metaheuristics (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s12351-019-00514-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:21:y:2021:i:4:d:10.1007_s12351-019-00514-z

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-019-00514-z

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().