A restart local search algorithm for solving maximum set k-covering problem |
| |
Authors: | Wang Yiyuan Ouyang Dantong Yin Minghao Zhang Liming Zhang Yonggang |
| |
Affiliation: | 1.College of Computer Science and Technology, Jilin University, Changchun, China ;2.Key Laboratory of Symbol Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, China ;3.School of Computer Science and Information Technology, Northeast Normal University, Changchun, China ; |
| |
Abstract: | The maximum set k-covering problem (MKCP) is a famous combinatorial optimization problem with widely many practical applications. In our work, we design a restart local search algorithm for solving MKCP, which is called RNKC. This algorithm effectively makes use of several advanced ideas deriving from the random restart mechanism and the neighborhood search method. RNKC designs a new random restart method to deal with the serious cycling problem of local search algorithms. Thanks to the novel neighborhood search method that allows a neighborhood exploration of as many feasible search areas as possible, the RNKC can obtain some greatly solution qualities. Comprehensive results on the classical instances show that the RNKC algorithm competes very favorably with a famous commercial solver CPLEX. In particular, it discovers some improved and great results and matches the same solution quality for some instances. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|