Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475472 | Computers & Operations Research | 2007 | 12 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Joaquín Bautista, Jordi Pereira,