The SWO solver used to produce the results reported in Table 1 restarted the priority queue every n/2 iterations, where nis the number of jobs in the problem. The same noisy heuristic that was used to initially populate the priority queue was also used to restart it. This restart cutoff was picked in a rather ad hoc manner. A more careful analysis of different restart cutoff values might lead to producing better solutions faster, and to some additional insight on the workings of SWO.
Restarts are often used in non-systematic search to avoid getting trapped in local optima or in cycles. (See parkes, 1996, for an empirical study of WSAT and further references.) Restarts have also been used in systematic search to escape exponentially large regions of the search space that do not contain a solution [Gomes, Selman, KautzGomes et al.1998].
Local optima pose little threat to SWO, since it is not directly driven by uphill/downhill considerations. SWO, through its use of large coherent moves, also tends to escape unpromising parts of the search space quickly. However, SWO is open to getting trapped in a cycle, and restarts are used as a means to escape them.
For these scheduling problems, SWO is unlikely to get into a tight cycle where priority queues and solutions repeat exactly. This is due to the presence of random tie breaking in several places, and to the presence of noise in the prioritizer. However, it is our belief that SWO can get trapped in a a cycle where similar priority queues and solutions repeat.
We ran a series of experiments with the 297 task problem to determine the impact of various restart cutoffs. The results are summarized in Table 2. Restart cutoffs ranged from after every 10 iterations to after every 1000 iterations. The success rate and mean cost are shown for each value for each of three different solution qualities. The success rate indicates the probability that a solution of at least the given quality was found in a given pass. The mean cost is the average number of total iterations to get a solution of that quality.
For the feasible and 18000 solution thresholds, SWO reaches a 100 percent success rate well before reaching the maximum restart cutoff of 1000 used in these experiments. In some sense, it is easy for SWO to produce solutions that are at least of these qualities. The results for these 2 thresholds indicate that when it is easy for SWO to solve the problem, any cutoff greater than the average number of uninterrupted iterations it takes to produce a solution can be used to solve the problem at minimum cost. For such ``easy'' problems, it appears that too small a restart cutoff can hurt, but that too big a cutoff will not.
The numbers for the 17700 solution quality threshold, tell a different story. The success rate is still climbing when the experiment ends, and the mean cost has actually risen above its minimum. For this solution quality, the restart cutoff that minimizes mean cost falls around the range of 70 to 100. Mean costs rise steeply for restart cutoffs below this range, and slowly for cutoffs larger than that. This is an example of a hard problem for SWO, and it shows that some care needs to be taken when choosing a restart strategy for such problems. Additional research is needed to determine how to set the restart cutoff automatically for arbitrary problems.
This data indicates that SWO does benefit from restarts, up to a point. With the 17700 threshold, for restart cutoffs up to 100, each increase in the cutoff in general led to a superlinear increase in the success rate. (This is also another indicator that SWO is learning from iteration to iteration.) Above 100 iterations per restart, the success rate initially climbs sublinearly and then appears to level out. It is an open question what this tells us about the search space.