An efficient local search heuristic with row weighting for the unicost set covering problem

Research output: Contribution to journalArticlepeer-review

Standard

An efficient local search heuristic with row weighting for the unicost set covering problem. / Gao, Chao; Yao, Xin; Weise, Thomas; Li, Jinlong.

In: European Journal of Operational Research, Vol. 246, No. 3, 01.11.2015, p. 750-761.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Bibtex

@article{c023e6bc8660472f8318425e5145e60b,
title = "An efficient local search heuristic with row weighting for the unicost set covering problem",
abstract = "The Set Covering Problem (SCP) is NP-hard. We propose a new Row Weighting Local Search (RWLS) algorithm for solving the unicost variant of the SCP, i.e., USCPs where the costs of all sets are identical. RWLS is a heuristic algorithm that has three major components united in its local search framework: (1) a weighting scheme, which updates the weights of uncovered elements to prevent convergence to local optima, (2) tabu strategies to avoid possible cycles during the search, and (3) a timestamp method to break ties when prioritizing sets. RWLS has been evaluated on a large number of problem instances from the OR-Library and compared with other approaches. It is able to find all the best known solutions (BKS) and improve 14 of them, although requiring a higher computational effort on several instances. RWLS is especially effective on the combinatorial OR-Library instances and can improve the best known solution to the hardest instance CYC11 considerably. RWLS is conceptually simple and has no instance-dependent parameters, which makes it a practical and easy-to-use USCP solver.",
keywords = "Combinatorial optimization, Row weighting local search, Unicost set covering problem",
author = "Chao Gao and Xin Yao and Thomas Weise and Jinlong Li",
year = "2015",
month = nov,
day = "1",
doi = "10.1016/j.ejor.2015.05.038",
language = "English",
volume = "246",
pages = "750--761",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

RIS

TY - JOUR

T1 - An efficient local search heuristic with row weighting for the unicost set covering problem

AU - Gao, Chao

AU - Yao, Xin

AU - Weise, Thomas

AU - Li, Jinlong

PY - 2015/11/1

Y1 - 2015/11/1

N2 - The Set Covering Problem (SCP) is NP-hard. We propose a new Row Weighting Local Search (RWLS) algorithm for solving the unicost variant of the SCP, i.e., USCPs where the costs of all sets are identical. RWLS is a heuristic algorithm that has three major components united in its local search framework: (1) a weighting scheme, which updates the weights of uncovered elements to prevent convergence to local optima, (2) tabu strategies to avoid possible cycles during the search, and (3) a timestamp method to break ties when prioritizing sets. RWLS has been evaluated on a large number of problem instances from the OR-Library and compared with other approaches. It is able to find all the best known solutions (BKS) and improve 14 of them, although requiring a higher computational effort on several instances. RWLS is especially effective on the combinatorial OR-Library instances and can improve the best known solution to the hardest instance CYC11 considerably. RWLS is conceptually simple and has no instance-dependent parameters, which makes it a practical and easy-to-use USCP solver.

AB - The Set Covering Problem (SCP) is NP-hard. We propose a new Row Weighting Local Search (RWLS) algorithm for solving the unicost variant of the SCP, i.e., USCPs where the costs of all sets are identical. RWLS is a heuristic algorithm that has three major components united in its local search framework: (1) a weighting scheme, which updates the weights of uncovered elements to prevent convergence to local optima, (2) tabu strategies to avoid possible cycles during the search, and (3) a timestamp method to break ties when prioritizing sets. RWLS has been evaluated on a large number of problem instances from the OR-Library and compared with other approaches. It is able to find all the best known solutions (BKS) and improve 14 of them, although requiring a higher computational effort on several instances. RWLS is especially effective on the combinatorial OR-Library instances and can improve the best known solution to the hardest instance CYC11 considerably. RWLS is conceptually simple and has no instance-dependent parameters, which makes it a practical and easy-to-use USCP solver.

KW - Combinatorial optimization

KW - Row weighting local search

KW - Unicost set covering problem

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

U2 - 10.1016/j.ejor.2015.05.038

DO - 10.1016/j.ejor.2015.05.038

M3 - Article

AN - SCOPUS:84932195536

VL - 246

SP - 750

EP - 761

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -