Restart strategies

Abstract

Restarting is a technique employed by many randomized algorithms for a variety of different problems. If the algorithm has not been successful after a certain time, the algorithm is reset, and a new try is started that is independent of the past attempt. For some problems, restarts can be used to achieve improved expected runtimes, while for others, restarts deteriorate the expected runtimes. For this reason, it is essential to gain insight into when restarts are beneficial and which restart strategy should be chosen.

In this thesis, we first show that the problem of deciding whether restarts have a positive effect is NP-hard, even when the underlying probability distribution is fully known. Furthermore, we prove that the computation of the expected runtime for a given restart strategy is #P-hard. On the other hand, an efficient (4+epsilon) approximation algorithm for the optimal restart strategy is provided.

In this context, we frequently assume that a given function is, in fact, a valid description of a probability distribution. The complexity of verifying these assumptions is also analyzed. We show that deciding whether a given function corresponds to a cumulative probability function is CoNP-hard. Moreover, deciding whether a given function represents a probability mass function is P(#P)-hard.

Although these problems are challenging in general, we show certain special cases in which they are simple. In particular, we introduce conditions for the usefulness of restarts as well as for determining an optimal restart strategy. It is shown that some typical parameters have either no or only a limited influence on the restart properties. Furthermore, it is proven that restarts are always useful for so-called long-tail distributions. By means of these results, it is possible to considerably simplify the analysis of many probability distributions; consequently, the NP-hardness does not pose an obstacle in many practical applications.

Luby's strategy is a popular restart strategy in practical applications. Suppose the underlying probability distribution is defined on the natural numbers. In that case, Luby's strategy provides a certain performance guarantee: The expected runtime using Luby's strategy is at most worse by a logarithmic factor than the expected runtime using the optimal restart strategy. However, we prove that this is not a general property, and furthermore, there is no universal restart strategy providing such a performance guarantee. On the other hand, we identify conditions under which such universal strategies do exist.

A particular obstacle for determining an optimal restart strategy is that the underlying probability distribution has to be known. However, that is usually not the case for unsolved instances. To circumvent this problem, we design a machine learning pipeline predicting the runtime distribution of unseen instances. An optimal restart strategy is derived for the SAT solver probSAT based on these predicted distributions. We experimentally demonstrate that this approach statistically significantly improves the performance of probSAT. We achieve an average speedup factor of more than 50 on the domain on which probSAT encounters the most significant difficulties.

Lastly, restarts are also considered in an environment in which a deadline is present and in which the corresponding algorithm runs in parallel. We specify a condition for finding the optimal restart strategy and show that increasing the number of utilized processors has a super-linear benefit in this scenario.