logo

SCIENCE CHINA Information Sciences, Volume 60, Issue 6: 062103(2017) https://doi.org/10.1007/s11432-015-5377-8

A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity

More info
  • ReceivedMar 27, 2016
  • AcceptedMay 8, 2016
  • PublishedFeb 9, 2017

Abstract

The unicost version of well-known set covering problem (SCP) is central to a wide variety of practical applications for which finding an optimal solution quickly is crucial. In this paper, we propose a new local search-based algorithm for the unicost SCP which follows the general framework of the popular stochastic local search with a particular focus on the hyperedge selection strategy and weight diversity strategy. Specifically, a strategy as called hyperedge configuration checking strategy is proposed here to avoid the search trajectory which leads to local optima. Additionally, a new weight diversity strategy is proposed for the diversification of search results, by changing the weight of both covered and uncovered vertices in the current solution. The experimental results show that our algorithm significantly outperforms the state-of-the-art heuristic algorithm by one to two orders of magnitudes on the 85 classical instances. Also, our algorithm improves the current optimal solutions of \linebreak 11 instances.


Acknowledgment

Acknowledgments

This work was supported in part by National Natural Science Foundation of China (Grant Nos. 61272208, 61370156, 61402196, 61503074, 61672261), Natural Science Foundation of Zhejiang Province (LY16F020004), and Program for New Century Excellent Talents in University (Grant No. NCET-13-0724). The authors of this paper express sincere gratitude to all the anonymous reviewers for their hard work.


References

[1] Karp R M. Reducibility among combinatorial problems. In: Complexity of Computer Computations. New York: Plenum Press, 1972. 85--103. Google Scholar

[2] Chakrabarty K. Test scheduling for core-based systems using mixed-integer linear programming. IEEE Trans Comput-Aided Des Integr Circuits Syst, 2000, 19: 1163-1174 CrossRef Google Scholar

[3] van Bevern R. Towards optimal and expressive kernelization for d-Hitting Set. Comput Comb, 2012, 7434: 121-132 Google Scholar

[4] Ausiello G, D'Atri A, Protasi M. Structure preserving reductions among convex optimization problems. J Comput Syst Sci, 1980, 21: 136-153 CrossRef Google Scholar

[5] Cai S W, Su K L, Luo C, et al. NuMVC: An efficient local search algorithm for minimum vertex cover. J Artif Intell Res, 2014, 46: 687-716 Google Scholar

[6] Dinur I, Safra S. On the hardness of approximating minimum vertex cover. Ann Math, 2005, 162: 439-485 CrossRef Google Scholar

[7] Caprara A, Fischetti M, Toth P. A heuristic method for the set covering problem. Oper Res, 1999, 47: 730-743 CrossRef Google Scholar

[8] Reiter R. A theory of diagnosis from first principles. Artif Intell, 1987, 32: 57-95 CrossRef Google Scholar

[9] Zhao X F, Ouyang D T. Improved algorithms for deriving all minimal conflict sets in model-based diagnosis. In: Proceedings of the Intelligent Computing 3rd International Conference on Advanced Intelligent Computing Theories and Applications. Berlin: Springer, 2007. 157--166. Google Scholar

[10] Angel E, Bampis E, Gourvès L. On the minimum hitting set of bundles problem. Theor Comput Sci, 2009, 410: 4534-4542 CrossRef Google Scholar

[11] Sellis T K. Multiple-query optimization. ACM Trans Database Syst, 1988, 13: 23-52 CrossRef Google Scholar

[12] Avella P, Boccia M, Vasilyev I. Computational experience with general cutting planes for the Set Covering problem. Oper Res Lett, 2009, 37: 16-20 CrossRef Google Scholar

[13] Bj{ö}rklund P, V{ä}rbrand P, Yuan D. A column generation method for spatial TDMA scheduling in ad hoc networks. Ad Hoc Netw, 2004, 2: 405-418 CrossRef Google Scholar

[14] Hemazro T D, Jaumard B, Marcotte O. A column generation and branch-and-cut algorithm for the channel assignment problem. Comput Oper Res, 2008, 35: 1204-1226 CrossRef Google Scholar

[15] Caprara A, Toth P, Fischetti M. Algorithms for the set covering problem. Ann Oper Res, 2000, 98: 353-371 CrossRef Google Scholar

[16] Pereira J, Averbakh I. The robust set covering problem with interval data. Ann Oper Res, 2013, 207: 217-235 CrossRef Google Scholar

[17] Yelbay S B, Birbil I, Bülbül K. The set covering problem revisited: an empirical study of the value of dual information. J Ind Manag Optimiz, 2015, 11: 575-594 Google Scholar

[18] Galinier P, Hertz A. Solution techniques for the large set covering problem. Discret Appl Mathematics, 2007, 155: 312-326 CrossRef Google Scholar

[19] Yagiura M, Kishida M, Ibaraki T. A 3-flip neighborhood local search for the set covering problem. Eur J Oper Res, 2006, 172: 472-499 CrossRef Google Scholar

[20] Kinney G W, Barnes J W, Colletti B W. A reactive tabu search algorithm with variable clustering for the unicost set covering problem. Int J Oper Res, 2007, 2: 156-172 CrossRef Google Scholar

[21] Caserta M. Tabu search-based metaheuristic algorithm for large-scale set covering problems. Metaheuristics Progress Complex Syst Opt, 2007, 39: 43-63 Google Scholar

[22] Umetani S, Yagiura M. Relaxation heuristics for the set covering problem. J Oper Res Soc Jpn, 2007, 50: 350-375 Google Scholar

[23] Lan G, DePuy G W, Whitehouse G E. An effective and simple heuristic for the set covering problem. Eur J Oper Res, 2007, 176: 1387-1403 CrossRef Google Scholar

[24] Bautista J, Pereira J. A GRASP algorithm to solve the unicost set covering problem. Comput Oper Res, 2007, 34: 3162-3173 CrossRef Google Scholar

[25] Ablanedo-Rosas J H, Rego C. Surrogate constraint normalization for the set covering problem. Eur J Oper Res, 2010, 205: 540-551 CrossRef Google Scholar

[26] Sundar S, Singh A. A hybrid heuristic for the set covering problem. Oper Res, 2012, 12: 345-365 Google Scholar

[27] Crawford B, Soto R, Cuesta R, et al. Application of the artificial bee colony algorithm for solving the set covering problem. Sci World J, 2014, 2014: 189164-365 Google Scholar

[28] Mulati M H, Constantino A A. Ant-Line: a line-oriented ACO algorithm for the set covering problem. In: Proceedings of the IEEE International Conference of the Chilean Computer Science Society, Curico, 2011. 265--274. Google Scholar

[29] Ren Z G, Feng Z R, Ke L J, et al. New ideas for applying ant colony optimization to the set covering problem. Comput Ind Eng, 2010, 58: 774-784 CrossRef Google Scholar

[30] Beasley J E, Chu P C. A genetic algorithm for the set covering problem. Eur J Oper Res, 1996, 94: 392-404 CrossRef Google Scholar

[31] Naji-Azimi Z, Toth P, Galli L. An electromagnetism metaheuristic for the unicost set covering problem. Eur J Oper Res, 2010, 205: 290-300 CrossRef Google Scholar

[32] Glover F. Tabu search-part I. ORSA J Comput, 1989, 1: 190-206 CrossRef Google Scholar

[33] Selman B, Kautz H A, Cohen B. Noise strategies for improving local search. In: Proceedings of National Conference on Artificial Intelligence, Seattle, 1994. 337--343. Google Scholar

[34] Cai S W, Su K L. Comprehensive score: towards efficient local search for sat with long clauses. In: Proceedings of the International Joint Conference on Artificial Intelligence, Beijing, 2013. 489--495. Google Scholar

[35] Cai S W, Su K L. Local search with configuration checking for SAT. In: Proceedings of the IEEE International Conference on Tools with Artificial Intelligence, Boca Raton, 2011. 59--66. Google Scholar

[36] Luo C, Cai S W, Wu W, et al. Double configuration checking in stochastic local search for satisfiability. In: Proceedings of National Conference on Artificial Intelligence, Qu$\acute{e}$bec, 2014. 2703--2709. Google Scholar

[37] Cai S W, Su K L. Local search for boolean satisfiability with configuration checking and subscore. Artif Intell, 2013, 204: 75-98 CrossRef Google Scholar

[38] Luo C, Cai S W, Su K L, et al. Clause states based configuration checking in local search for satisfiability. IEEE Trans cybern, 2014, 45: 1014-1027 Google Scholar

[39] Luo C, Cai S W, Wu W, et al. CCLS: an efficient local search algorithm for weighted maximum satisfiability. IEEE Trans Comput, 2015, 64: 1830-1843 CrossRef Google Scholar

[40] Beasley J E. OR-Library: distributing test problems by electronic mail. J Oper Res Soc, 1990, 41: 1069-1072 CrossRef Google Scholar

[41] Xu K, Boussemart F, Hemery F, et al. A simple model to generate hard satisfiable instances. In: Proceedings of the International Joint Conference on Artificial Intelligence, Edinburgh, 2005. 337--342. Google Scholar

[42] Selman B, Levesque H J, Mitchell D G. A new method for solving hard satisfiability problems. In: Proceedings of National Conference on Artificial Intelligence, San Jose, 1992. 440--446. Google Scholar

[43] Li C M, Huang W Q. Diversification and determinism in local search for satisfiability. Lect Notes Comput Sci, 2005, 3569: 158-172 CrossRef Google Scholar

[44] Gent I P, Walsh T. Towards an understanding of hill-climbing procedures for SAT. In: Proceedings of National Conference on Artificial Intelligence, Washington, 1993. 28--33. Google Scholar

[45] Cai S W, Su K L, Sattar A. Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artif Intell, 2011, 175: 1672-1696 CrossRef Google Scholar

[46] Xu K, Li W. Many hard examples in exact phase transitions. Theor Comput Sci, 2006, 355: 291-302 CrossRef Google Scholar

[47] Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res, 2000, 12: 93-103 Google Scholar

[48] Xu K, Boussemart F, Hemery F, et al. Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell, 2007, 171: 514-534 CrossRef Google Scholar

[49] Gao J, Wang J N, Yin M H. Experimental analyses on phase transitions in compiling satisfiability problems. Sci China Inf Sci, 2015, 58: 032104-534 Google Scholar

[50] Huang P, Yin M H. An upper (lower) bound for Max (Min) CSP. Sci China Inf Sci, 2014, 57: 072109-534 Google Scholar

[51] Grossman T, Wool A. Computational experience with approximation algorithms for the set covering problem. Eur J Oper Res, 1997, 101: 81-92 CrossRef Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1