A GRASP algorithm to solve the unicost set covering problem |
| |
Authors: | Joaquín Bautista Jordi Pereira |
| |
Affiliation: | Escola Tècnica Superior d’Enginyers Industrials de Barcelona, Universitat Politècnica de Catalunya, Av. Diagonal 647, 7th floor, 08028 Barcelona, Spain |
| |
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. |
| |
Keywords: | Set covering Optimization Constraint satisfaction |
本文献已被 ScienceDirect 等数据库收录! |