Abstract
In combinatorial search, deterministic algorithms often exhibit highly erratic performance, where nearly identical problem instances result in vastly different solution times. This paper identifies heavy-tailed cost distributions as the primary cause of this phenomenon. By introducing controlled randomization and a strategy of rapid restarts with fixed cutoffs, the authors demonstrate how to exploit the high variance of these distributions to achieve performance gains of several orders of magnitude on notoriously difficult NP-complete problems.
The Problem: Heavy-Tailed Cost Distributions
Combinatorial search problems, such as circuit synthesis or sports scheduling, frequently encounter a "stuck" behavior where a solver takes days to solve a problem that should seemingly take seconds. The authors argue that this is not necessarily a property of the problem instance's inherent hardness, but rather a property of the search process itself.
Deterministic algorithms often become trapped in massive sub-trees of the search space that contain no solutions. Because the algorithm follows a fixed path, it is forced to explore the entire dead-end every time. This leads to heavy-tailed distributions, characterized by a non-negligible probability of a run taking exponentially longer than the median time. In such distributions, the mean solution time can become effectively infinite.
Methodology: Randomization and Rapid Restarts
To mitigate the impact of heavy tails, the authors propose transforming standard "complete" search engines (like SAT or Constraint Satisfaction solvers) into randomized versions using two primary techniques:
- Controlled Randomization: The solver's deterministic tie-breaking rules are replaced with random choices. If a heuristic is particularly sharp, a parameter $H$ is introduced to treat any choice within $H\%$ of the best score as equally viable for random selection.
- Rapid Restarts with Cutoffs ($c$): The algorithm is assigned a budget of $c$ backtracks. If no solution is found within this limit, the search is aborted and restarted from the root with a new random seed. This prevents the solver from remaining stuck in a heavy-tail dead-end and allows it to "fish" for the short paths to a solution that exist in the distribution's left tail.
Experimental Results
The approach was evaluated on several difficult domains, including logistics planning, circuit synthesis (3-bit adder), and round-robin sports scheduling. The results, summarized below, show that randomization can turn effectively unsolvable problems into manageable ones.
In the case of the 3-bit adder synthesis, the deterministic solver failed to find a solution within 24 hours. By contrast, the randomized version with restarts found a solution in a mean time of just 165 seconds. This dramatic speedup confirms that the "hardness" was a result of the search path rather than the problem instance.
Key Insights and Discussion
The success of this method relies on exploiting the "left tail" of the distribution. While heavy tails imply some runs are incredibly long, they also imply that a small percentage of runs are incredibly short. Restarts allow the solver to sample multiple paths until it hits one of these lucky, short runs.
However, the strategy requires finding a "sweet spot" for the cutoff value $c$. If the cutoff is too low, the solver may never reach the depth required for a solution; if it is too high, the solver risks entering the heavy-tail region. While finding the optimal $c$ often requires trial and error, the authors suggest that a strategy of gradually increasing the cutoff can be a robust practical alternative.
Conclusion
By acknowledging that search complexity is a stochastic variable, researchers can use randomization and restarts to "hack" the underlying probability distributions of combinatorial problems. While not a universal fix—some domains like "Blocks-World" do not exhibit heavy tails and thus do not benefit—this technique remains a powerful tool for boosting the efficiency of state-of-the-art search engines.
Summary updated