A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search

Tobias Friedrich, Timo Kötzing, Markus WagnerAAAI 2017 · DOI

Introduction

Stochastic local search (SLS) heuristics are fundamental to solving NP-complete optimization problems. However, these algorithms are often highly sensitive to their starting conditions; a poor initialization can lead to the search becoming trapped in suboptimal regions for extended periods. While restart strategies are commonly employed to mitigate this, finding the optimal balance between a single long run and many short runs remains a challenge. This paper presents a "bet-and-run" framework that bridges this gap by using a small initial time budget to "scout" the search space.

The Bet-and-Run Framework

The proposed strategy operates in two distinct phases:

  1. Phase 1 (The Bet): The algorithm executes $k$ independent, randomized runs for a short duration $t_1$.
  2. Phase 2 (The Run): The best-performing run from Phase 1 is identified. This run is then continued for the remaining time budget $t_2 = t - (k \cdot t_1)$.
The Bet-and-Run Framework: Phase 1 involves k short runs to identify the most promising candidate, which is then extended in Phase 2.

To ensure the strategy is "off-the-shelf" and compatible with black-box solvers, the authors implement Phase 2 by restarting the best run from its original random seed and running it for the total duration $t_1 + t_2$. This avoids the need for complex state-saving mechanisms within the solver.

Experimental Evaluation

The strategy was evaluated on two classic NP-complete problems:

  • Traveling Salesperson Problem (TSP): Using the Chained-Lin-Kernighan (CLK) heuristic on large instances from TSPlib (up to 100,000 cities).
  • Minimum Vertex Cover (MVC): Using the FASTVC solver on massive real-world graphs, including social networks and web crawls.

The performance was compared against standard single-run, multi-run, and Luby-sequence-based restart strategies.

Results and Discussion

The "bet-and-run" approach consistently outperformed the single-run baseline. A particularly robust configuration emerged: performing 40 short runs, each consuming 1% of the total budget (RESTARTS$^{40}_{1\%}$).

Performance Heatmaps for TSP: These plots show the absolute distance to the best-known solution for the 'pla33810' instance across different time budgets (20s, 40s, 60s). The x-axis represents the number of restarts in Phase 1, and the y-axis represents the time budget per restart. Blue regions indicate better performance.

For TSP, the heatmaps reveal that spending a significant portion of the budget (up to 40%) on the betting phase can be beneficial. In MVC, the strategy proved even more resilient, showing gains across a wide range of parameter settings. Statistical analysis using the Wilcoxon rank-sum test confirmed that the bet-and-run strategy was significantly better than no restarts in the majority of tested instances.

Conclusion

The bet-and-run framework provides a simple, generic, and effective method for improving the performance of SLS solvers. By treating the underlying solver as a black box, it achieves significant speedups without problem-specific tuning. Future research could explore dynamic versions of this strategy, such as early stopping for underperforming runs or hierarchical betting phases to further optimize the allocation of the time budget.

Summary updated

BibTeX
@inproceedings{friedrich2017generic,
  author = {Tobias Friedrich and Timo Kötzing and Markus Wagner},
  title = {{A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10645},
}
Figure