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

作     者：Yiyuan WANG Dantong OUYANG Liming ZHANG Minghao YIN 

作者机构：Symbol Computation and Knowledge Engineer of Ministry of Education Jilin University College of Computer Science and Technology Jilin University School of Computer Science and Information Technology Northeast Normal University 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2017年第60卷第6期

页      面：145-158页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported in part by National Natural Science Foundation of China (Grant Nos. 61272208, 61370156, 61402196, 61503074, 61672261) Natural Science Foundation of Zhejiang Province (LY16F020004) Program for New Century Excellent Talents in University (Grant No. NCET-13-0724) 

主　　题：unicost set covering problem hyperedge configuration checking local search weight diversity strategy hyperedge selection strategy 

摘      要：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 searchbased 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 of11 instances.