Boosting Combinatorial Search Through Randomization

Carla P. Gomes, Bart Selman, Henry A. Kautz

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.

Log-log plot of the survival function 1-F(x) against backtracks, illustrating the heavy-tailed nature of the search cost distribution.

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:

  1. 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.
  2. 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.

Comparison of deterministic solution times versus randomized mean solution times across various problem domains.

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

Abstract

Unpredictability in the running time of complete search procedures can often be explained by the phenomenon of "heavy-tailed cost distributions", meaning that at any time during the experiment there is a non-negligible probability of hitting a problem that requires exponentially more time to solve than any that has been encountered before (Gomes et al. 1998a). We present a general method for introducing controlled randomization into complete search algorithms. The "boosted" search methods provably eliminate heavy-tails to the right of the median. Furthermore, they can take advantage of heavy-tails to the left of the median (that is, a nonnegligible chance of very short runs) to dramatically shorten the solution time. We demonstrate speedups of several orders of magnitude for state-of-the-art complete search procedures running on hard, real-world problems.
BibTeX
@inproceedings{gomes1998boosting,
  author = {Carla P. Gomes and Bart Selman and Henry A. Kautz},
  title = {{Boosting Combinatorial Search Through Randomization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure