Research map / Learning theory and algorithms / Combinatorial and search optimization
A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use diminishing-returns prediction instead of currentBest run selection | Bet-and-Run · MVC | instances significantly better or worse than F17: 43 instances; worse only on 24 instances | Helped |
| Use perceptron-based decision makers instead of currentBest | Bet-and-Run · MVC, initial budget 40s, 100s, or 400s | frequency of outperforming a single run with full budget | Helped |
| Use perceptron-based decision makers instead of currentBest | Bet-and-Run · TSP, initial budget 400s | frequency of outperforming a single run with full budget | Helped |
| Use more elaborate predictors instead of currentBest | Bet-and-Run with 4 initial runs · MVC and TSP, small and large total time budgets | final quality gap to best possible solution | Helped |
| Use diminishing-returns prediction instead of F17 | Bet-and-Run · TSP, total budget 2'000s | instances where F17 is better or worse: F17 is better on only three instances; being beaten on 19 instances | Helped |
| Continue the selected run after the initialization phase rather than only making independent restarts | Bet-and-Run · MVC and TSP, short total runtime | final quality gap to best possible solution | Helped |
| Increase decision-maker complexity and account for its runtime cost | Bet-and-Run · MVC and TSP | final solution outcome | No clear effect |
| Use Even budgeting with 10 initial runs and continue 1 | Bet-and-Run · MVC, total budget 40s or 100s; TSP, total budget 10s or 40s | average score over decision makers | Helped |
| Continue 2 runs rather than 1 | Bet-and-Run · MVC and TSP, total budget 400s | average score over decision makers | Helped |
| Use currentBest rather than a more sophisticated decision maker | Bet-and-Run · Across benchmark instances and configurations | relative performance | Mixed |
| Use diminishing-returns prediction rather than F17 | Bet-and-Run · MVC | instances significantly better or worse than F17: 43 instances; worse only on 24 instances | Mixed |
Closest papers by meaning
- An Improved Generic Bet-and-Run Strategy with Performance Prediction for Stochastic Local Search (AAAI 2019 · similarity 0.93)
- On the Universal Near Optimality of Hedge in Combinatorial Settings (NeurIPS 2025 · similarity 0.86)
- A General Large Neighborhood Search Framework for Solving Integer Linear Programs (NeurIPS 2020 · similarity 0.86)
- Revisiting Sampling for Combinatorial Optimization (ICML 2023 · similarity 0.86)
- Buying Information for Stochastic Optimization (ICML 2023 · similarity 0.86)
- Random is Faster than Systematic in Multi-Objective Local Search (AAAI 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.