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

Chao GAO, Xin YAO, Thomas WEISE, Jinlong LI

Research output: Journal PublicationsJournal Article (refereed)peer-review

45 Citations (Scopus)

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. © 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.
Original languageEnglish
Pages (from-to)750-761
Number of pages12
JournalEuropean Journal of Operational Research
Volume246
Issue number3
Early online date23 May 2015
DOIs
Publication statusPublished - Nov 2015
Externally publishedYes

Bibliographical note

This research work was supported by an EPSRC grant (No. EP/I010297/1 ), an EU FP7 IRSES grant (No. 247619) and the Fundamental Research Funds for the Central Universities (WK0110000023). Xin Yao was supported by a Royal Society Wolfson Research Merit Award. Thomas Weise was supported by the National Natural Science Foundation of China under Grants 61150110488 and 61329302 , the Special Financial Grant 201104329 from the China Postdoctoral Science Foundation , and the Chinese Academy of Sciences (CAS) Fellowship for Young International Scientists 2011Y1GB01 .

Keywords

  • Combinatorial optimization
  • Row weighting local search
  • Unicost set covering problem

Fingerprint

Dive into the research topics of 'An efficient local search heuristic with row weighting for the unicost set covering problem'. Together they form a unique fingerprint.

Cite this