What Are We Trying to Optimize by Restarting (A Real - And Fun - Experimental Set Up)

Despite the importance of restart strategies in modern SAT solvers, even simple questions about when to restart and why we should restart is known. For instance, the fact that the Luby restart strategy is still very successful only states that we are blindly firing restarts. A few informed strategies have been proposed but there are no (experimentally stong) explanations of their success. In this presentation, we present a costly but funny experimental study of what restart strategies can and should do to help the search. We will uncover some surprising results.