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

Authors

  • Tobias Friedrich Hasso Plattner Institute
  • Timo Kötzing Hasso Plattner Institute
  • Markus Wagner The University of Adelaide

DOI:

https://doi.org/10.1609/aaai.v31i1.10645

Keywords:

heuristic search, erraticism

Abstract

A common strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. However, while specific restart strategies have been developed for specific problems (and specific algorithms), restarts are typically not regarded as a general tool to speed up an optimization algorithm. In fact, many optimization algorithms do not employ restarts at all. Recently, "bet-and-run" was introduced in the context of mixed-integer programming, where first a number of short runs with randomized initial conditions is made, and then the most promising run of these is continued. In this article, we consider two classical NP-complete combinatorial optimization problems, traveling salesperson and minimum vertex cover, and study the effectiveness of different bet-and-run strategies. In particular, our restart strategies do not take any problem knowledge into account, nor are tailored to the optimization algorithm. Therefore, they can be used off-the-shelf. We observe that state-of-the-art solvers for these problems can benefit significantly from restarts on standard benchmark instances.

Downloads

Published

2017-02-12

How to Cite

Friedrich, T., Kötzing, T., & Wagner, M. (2017). A Generic Bet-and-Run Strategy for Speeding Up Stochastic Local Search. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10645

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization