Local Search with Efficient Automatic Configuration for Minimum Vertex Cover

Local Search with Efficient Automatic Configuration for Minimum Vertex Cover

Chuan Luo, Holger H. Hoos, Shaowei Cai, Qingwei Lin, Hongyu Zhang, Dongmei Zhang

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1297-1304. https://doi.org/10.24963/ijcai.2019/180

Minimum vertex cover (MinVC) is a prominent NP-hard problem in artificial intelligence, with considerable importance in applications. Local search solvers define the state of the art in solving MinVC. However, there is no single MinVC solver that works best across all types of MinVC instances, and finding the most suitable solver for a given application poses considerable challenges. In this work, we present a new local search framework for MinVC called MetaVC, which is highly parametric and incorporates many effective local search techniques. Using an automatic algorithm configurator, the performance of MetaVC can be optimized for particular types of MinVC instances. Through extensive experiments, we demonstrate that MetaVC significantly outperforms previous solvers on medium-size hard MinVC instances, and shows competitive performance on large MinVC instances. We further introduce a neural-network-based approach for enhancing the automatic configuration process, by identifying and terminating unpromising configuration runs. Our results demonstrate that MetaVC, when automatically configured using this method, can achieve improvements in the best known solutions for 16 large MinVC instances.
Keywords:
Heuristic Search and Game Playing: Heuristic Search
Heuristic Search and Game Playing: Heuristic Search and Machine Learning
Heuristic Search and Game Playing: Combinatorial Search and Optimisation
Heuristic Search and Game Playing: Meta-Reasoning and Meta-heuristics