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.
Bibliographical noteThis 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 .
- Combinatorial optimization
- Row weighting local search
- Unicost set covering problem