A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search
Authors: Tobias Friedrich, Timo Ktzing, Markus Wagner
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We benchmark our strategies on two different problems: traveling sales person (TSP) and minimum vertex cover (MVC). We observe statistically significant improvements of our bet-and-run strategy on standard corpora for state-of-the-art solvers for both optimization problems. |
| Researcher Affiliation | Academia | 1Hasso Plattner Institute, Potsdam, Germany 2Optimisation and Logistics, The University of Adelaide, Adelaide, Australia |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | Our code and results have been made publicly available: http://bitbucket.org/markuswagner/restarts |
| Open Datasets | Yes | The TSPlib is a classic repository of TSP instances (Reinelt 1991), which are available online (Reinelt 2008). ... All instances are available online (Rossi and Ahmed 2015). |
| Dataset Splits | No | The paper describes using 100 independent repetitions for statistical analysis but does not specify training/validation/test dataset splits. The methodology involves running algorithms on benchmark instances rather than training on a split portion of data. |
| Hardware Specification | Yes | on a compute cluster with Intel Xeon E5620 CPUs (2.4GHz). |
| Software Dependencies | No | The paper mentions using CLK and FASTVC solvers, but does not provide specific version numbers for these or any other software dependencies like programming languages or libraries. |
| Experiment Setup | Yes | For each heatmap we use one fixed total time budget, and we systematically vary the number of runs in the first phase and their run times. In each plot we show a diagonal line that indicates the schemes RESTARTSx 1/x, which corresponds to performing x independent runs with each 1/x-th of the total budget... Our considered overall run time budgets are 100 tinit, 400 tinit, 1 000 tinit, 4 000 tinit, and 10 000 tinit. |