Article ID: | iaor20083357 |
Country: | United Kingdom |
Volume: | 34 |
Issue: | 10 |
Start Page Number: | 3162 |
End Page Number: | 3173 |
Publication Date: | Oct 2007 |
Journal: | Computers and Operations Research |
Authors: | Bautista Joaqun, Pereira Jordi |
Keywords: | sets, programming: constraints |
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. 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.