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'' entries6. 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 log-b and impressive speedup on log-c, 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 log-c five of the twenty ``Raw'' runs lasted longer than the longest ``Cutoff doubling'' run.