Because LPSAT uses a randomized backtracking algorithm and because early experimental results showed a small percentage of runs far exceeded the median runtime, we experimented with random restarts using a process similar to the one described in [Gomes et al.1998]. We cut off solving at a deadline  which can be either fixed beforehand or geometrically increasing  and restart the solver with a new random seed.
0.55figs/restart3.eps

Figure 8 shows the results of these experiments. We first ran the algorithm twenty times on each problem to produce the ``Raw'' entries^{6}. Then, we calculated the cutoff time which minimized the expected runtime of the system based on these twenty runs. Finally, we reran the problems with this tuned cutoff time to produce the ``Tuned Cutoff'' data.
While this technique provides some speedup on logb and impressive speedup on logc, it requires substantial, preliminary research into the difficulty of the problem (in order to determine the appropriate cutoff time). Unless LPSAT is being used repeatedly to solve a single problem or several very similar problems, the process of finding good restart times will dominate overall runtime.
Therefore, we also experimented with a restart system which requires no prior analysis. This ``Cutoff doubling'' approach sets an initial restart limit of one second and increases that limit by a factor of two on each restart until reaching a solution. We have not yet performed any theoretical analysis of the effectiveness of this technique, but Figure 8 demonstrates a small improvement. More interesting than the average improvement, however, is the fact that this method improved the consistency of the runtimes on the harder problems; indeed, on logc five of the twenty ``Raw'' runs lasted longer than the longest ``Cutoff doubling'' run.