A Fast and Robust Heuristic Algorithm for the Minimum Weight Vertex Cover Problem
Open Access
- 14 January 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 9, 31932-31945
- https://doi.org/10.1109/access.2021.3051741
Abstract
The minimum weight vertex cover problem (MWVCP) is a fundamental combinatorial optimization problem with various real-world applications. The MWVCP seeks a vertex cover of an undirected graph such that the sum of the weights of the selected vertices is as small as possible. In this paper, we present an effective algorithm to solve the MWVCP. First, a master-apprentice evolutionary algorithm based on two individuals is conducted to enhance the diversity of solutions. Second, a hybrid tabu search combined configuration checking and solution-based tabu search is introduced to intensify local search procedure. Harnessing the power of the evolutionary strategy and a novel variant of hybrid tabu search, Master-Apprentice Evolutionary Algorithm with Hybrid Tabu Search, MAE-HTS, is presented. Results of extensive computational experiments using standard benchmark instances and other large-scale instances demonstrate the efficacy of our algorithm in terms of solution quality, running time, and robustness compared to state-of-the-art heuristics from the literature and the commercial MIP solver Gurobi. We also systematically analyze the role of each individual component of the algorithm which when worked in unison produced superior outcomes. In particular, MAE-HTS produced improved solutions for 2 out of 126 public benchmark instances with better running time. In addition, our MAE-HTS outperforms other state-of-the-art algorithms DLSWCC and NuMWVC for 72 large scale MWVCP instances by obtaining the best results for 64 ones, while other two reference algorithms can only obtain 27 best results at most.Funding Information
- Natural Sciences and Engineering Research Council [Discovery Grant and Discovery Accelerator Supplement]
This publication has 34 references indexed in Scilit:
- A population-based iterated greedy algorithm for the minimum weight vertex cover problemApplied Soft Computing, 2012
- An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problemApplied Soft Computing, 2011
- A hybrid metaheuristic approach to solving the UBQP problemEuropean Journal of Operational Research, 2010
- A memetic algorithm for graph coloringEuropean Journal of Operational Research, 2010
- A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEMAsia-Pacific Journal of Operational Research, 2006
- An efficient simulated annealing algorithm for the minimum vertex cover problemNeurocomputing, 2006
- A Tutorial for Competent Memetic Algorithms: Model, Taxonomy, and Design IssuesIEEE Transactions on Evolutionary Computation, 2005
- An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover ProblemAnnals of Operations Research, 2004
- On efficient fixed-parameter algorithms for weighted vertex coverJournal of Algorithms, 2003
- Greedy Randomized Adaptive Search ProceduresJournal of Global Optimization, 1995