Paper Info
Title
A GRASP algorithm to solve the unicost set covering problem
Abstract
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.
Year
DOI
Venue
2007
10.1016/j.cor.2005.11.026
Computers & OR
Keywords
Field
DocType
binary constraint satisfiability problem,special SCP case,local improvement procedure,reference instance,best-known solution,well-known combinatorial optimization problem,proposed algorithm,GRASP algorithm
Set cover problem,Constraint satisfaction,Mathematical optimization,GRASP,Combinatorial optimization problem,Algorithm,Mathematics
Journal
Volume
Issue
ISSN
34
10
Computers and Operations Research
Citations 
PageRank 
References 
22
1.07
13
Authors
2
Name
Order
Citations
PageRank
Joaquín Bautista134527.50
Jordi Pereira225219.64