Local Search with Efficient Automatic Configuration for Minimum Vertex Cover
Authors: Chuan Luo, Holger H. Hoos, Shaowei Cai, Qingwei Lin, Hongyu Zhang, Dongmei Zhang
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Through extensive experiments, we demonstrate that Meta VC significantly outperforms previous solvers on medium-size hard Min VC instances, and shows competitive performance on large Min VC instances. |
| Researcher Affiliation | Collaboration | 1Microsoft Research, China 2Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands 3Department of Computer Science, University of British Columbia, Canada 4State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China 5The University of Newcastle, Australia |
| Pseudocode | Yes | Algorithm 1 The pseudo-code of Meta VC framework |
| Open Source Code | Yes | The implementation of Meta VC and additional information are available at https://github.com/chuanluocs/Meta VC. |
| Open Datasets | Yes | DIMACS-HARD: The 8 hardest instances from the DIMACS benchmark,3 which is taken from the the Second DIMACS Challenge Test Problems. ...3http://lcs.ios.ac.cn/~caisw/Resource/DIMACS% 20complementary%20graphs.tar.gz |
| Dataset Splits | Yes | To configure Meta VC, we needed to construct a training set for each benchmark. For DIMACS-HARD, BHOSLIB-HARD and REAL-WORLD-HARD, we selected 3, 5 and 12 instances, respectively. ... Each of the resulting configurations was evaluated on all training instances. |
| Hardware Specification | Yes | In this work, all our experiments were carried out on a cluster of computers, where each computer is equipped with 32 Intel Xeon E5-2683 CPUs and 94 GB memory |
| Software Dependencies | Yes | running the operating system of Cent OS 7.6.1810. For our experiments, we chose 3 prominent benchmarks... To maximize performance for a given class of benchmark instances, we used a state-of-the-art automatic algorithm configurator called SMAC [Hutter et al., 2011] to configure Meta VC. |
| Experiment Setup | Yes | For each solver, we performed 100 independent runs per instance, with a cutoff time of one hour per run. ... T, t, r and δ were set to 300, 30, 10 and 0.0001, respectively. |