  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.
