A GRASP algorithm to solve the unicost set covering problem

A GRASP algorithm to solve the unicost set covering problem

0.00 Avg rating0 Votes
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: ,
Keywords: sets, programming: constraints
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. 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.

Reviews

Required fields are marked *. Your email address will not be published.