Local Search with Efficient Automatic Configuration for Minimum Vertex Cover

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 instances, and shows competitive performance on large application instances. We further introduce a novel, neural network based method for enhancing the automatic configuration process, by identifying and terminating unpromising configuration runs. Our results present that MetaVC with the optimized configuration obtained using this method, called MetaVC2, can achieve improvements in the best known solutions for 16 large application instances.