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:
- Phase 1 (The Bet): The algorithm executes $k$ independent, randomized runs for a short duration $t_1$.
- 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)$.
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\%}$).
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