Towards Ultra Rapid Restarts
This is an incremental analysis for SAT solver developers, highlighting a performance trend without introducing new methods.
The paper examines the trend of increasingly rapid restart strategies in SAT solvers, noting that modern solvers restart after a dozen backtracks for better performance, with experimental results supporting this observation.
We observe a trend regarding restart strategies used in SAT solvers. A few years ago, most state-of-the-art solvers restarted on average after a few thousands of backtracks. Currently, restarting after a dozen backtracks results in much better performance. The main reason for this trend is that heuristics and data structures have become more restart-friendly. We expect further continuation of this trend, so future SAT solvers will restart even more rapidly. Additionally, we present experimental results to support our observations.