A GRASP algorithm to solve the unicost set covering problem

Joaquín Bautista, Jordi Pereira

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


The set covering problem (SCP) is a well-known combinatorial optimization problem. This paper presents a GRASP algorithm to solve a special SCP case known in the literature as the unicost set covering problem. The algorithm incorporates a local improvement procedure based on the heuristics to solve binary constraint satisfiability problems (SAT). The quality of the proposed algorithm is tested on a set of reference instances, comparing the obtained results with those found in the literature. Our algorithm improves the best-known solutions for many of these instances.

Original languageEnglish
Pages (from-to)3162-3173
Number of pages12
JournalComputers and Operations Research
Issue number10
StatePublished - Oct 2007
Externally publishedYes


  • Constraint satisfaction
  • Optimization
  • Set covering


Dive into the research topics of 'A GRASP algorithm to solve the unicost set covering problem'. Together they form a unique fingerprint.

Cite this