A GRASP algorithm to solve the unicost set covering problem

Joaquín Bautista; Jordi Pereira

doi:10.1016/j.cor.2005.11.026

A GRASP algorithm to solve the unicost set covering problem

Joaquín Bautista, Jordi Pereira

Research output: Contribution to journal › Article › peer-review

40 Scopus citations

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.

Original language	English
Pages (from-to)	3162-3173
Number of pages	12
Journal	Computers and Operations Research
Volume	34
Issue number	10
DOIs	https://doi.org/10.1016/j.cor.2005.11.026
State	Published - Oct 2007
Externally published	Yes

Keywords

Constraint satisfaction
Optimization
Set covering

Access to Document

10.1016/j.cor.2005.11.026

Cite this

@article{b14bfeb8ea3c4eb098d4f3195f40941c,

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.",

keywords = "Constraint satisfaction, Optimization, Set covering",

author = "Joaqu{\'i}n Bautista and Jordi Pereira",

note = "Funding Information: This work was partly funded by Grants BEC2003-03809 and DPI2004-03475 from the Spanish Government. We thank Nissan Spain and the UPC Nissan Chair for their help in this research work. Finally, we greatly acknowledge the substantial suggestions received by the referee of the paper.",

year = "2007",

month = oct,

doi = "10.1016/j.cor.2005.11.026",

language = "English",

volume = "34",

pages = "3162--3173",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd.",

number = "10",

}

TY - JOUR

T1 - A GRASP algorithm to solve the unicost set covering problem

AU - Bautista, Joaquín

AU - Pereira, Jordi

N1 - Funding Information: This work was partly funded by Grants BEC2003-03809 and DPI2004-03475 from the Spanish Government. We thank Nissan Spain and the UPC Nissan Chair for their help in this research work. Finally, we greatly acknowledge the substantial suggestions received by the referee of the paper.

PY - 2007/10

Y1 - 2007/10

N2 - 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.

AB - 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.

KW - Constraint satisfaction

KW - Optimization

KW - Set covering

UR - http://www.scopus.com/inward/record.url?scp=33847674937&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2005.11.026

DO - 10.1016/j.cor.2005.11.026

M3 - Article

AN - SCOPUS:33847674937

SN - 0305-0548

VL - 34

SP - 3162

EP - 3173

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 10

ER -

A GRASP algorithm to solve the unicost set covering problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this