Expected Gains from Parallelizing Constraint Solving for Hard Problems

Tad Hogg, Colin P. WilliamsAAAI 1994

Abstract

This paper investigates the efficacy of independent parallel search and restart strategies for solving NP-hard constraint satisfaction problems, specifically 3-coloring. By analyzing the full probability distribution of search costs, we demonstrate that the success of parallelization depends on the problem's structural properties. In regions where cost distributions are multimodal, parallelization offers significant speedups. Conversely, in "intrinsically hard" regions characterized by unimodal distributions, simple parallelization provides minimal benefit.

Introduction

In the study of NP-hard problems like graph coloring and SAT, researchers have identified "phase transitions" where problem difficulty shifts dramatically based on structural parameters, such as graph connectivity. While average-case complexity provides some insight, it fails to capture the variance that dictates the success of heuristic search. This study explores whether running $k$ independent agents in parallel can exploit this variance to find solutions faster.

Methodology

The authors utilized the 3-coloring problem on randomly generated 100-node graphs. The search algorithm employed was a complete depth-first backtracking search using the Brelaz heuristic. Two primary strategies were evaluated:

  1. Independent Parallel Search: $k$ agents search the same instance simultaneously with different random seeds. The process stops when the first agent finds a solution.
  2. Restart Strategy: A single agent restarts the search from scratch if a solution is not found within a specified time limit $\tau$.

The analysis focused on the average connectivity ($\gamma$) of the graphs, specifically comparing the "easy" region ($\gamma = 3.5$) with occasional high-cost "monsters" to the "critically hard" region ($\gamma = 4.5$) near the phase transition.

Structural Insights: Multimodal vs. Unimodal Distributions

A key finding is that the shape of the search cost distribution determines the potential for speedup. At lower connectivities ($\gamma = 3.5$), the distribution is often multimodal. Most searches finish quickly, but a few become trapped in exceptionally long paths. In contrast, at the critical connectivity ($\gamma = 4.5$), the distribution becomes unimodal, where almost all search paths are similarly long and difficult.

Figure 4: Comparison of search cost distributions. The top panel shows a multimodal distribution (log scale) typical of lower connectivity regions, while the bottom panel shows a unimodal distribution characteristic of the critically hard region.

Parallelization acts as a "variance eater." In multimodal distributions, having multiple agents increases the probability that at least one will follow a "lucky" fast path. In unimodal distributions, every agent is likely to encounter the same level of difficulty, rendering parallelization ineffective.

Parallelization and Speedup Results

The empirical results confirm that the effectiveness of parallelization is highly instance-dependent. At $\gamma = 3.5$, parallel agents could achieve speedups of 20x or more for the most difficult instances. However, at $\gamma = 4.5$, the speedup often hovered near 1.0, regardless of the number of agents.

Figure 5: Speedup achieved by parallel agents plotted against the original search cost. Significant speedups are observed for high-cost instances in multimodal regions, whereas speedup remains low for intrinsically hard instances.

The "intrinsically hard" nature of the $\gamma = 4.5$ region is hypothesized to stem from the presence of many large partial solutions that mislead heuristics into deep, fruitless branches. These "dead ends" are pervasive, making the problem difficult for any independent agent.

Conclusion

Parallelizing search for NP-hard problems is not a universal solution. Its utility is constrained by the underlying cost distribution of the problem instances. While independent parallel search and restart strategies are powerful tools for "hit-or-miss" problems, they fail against "intrinsically hard" instances. Future work should focus on cooperative problem solving, where agents share information to prune the search space more effectively in these difficult regions.

Summary updated

BibTeX
@inproceedings{hogg1994expected,
  author = {Tad Hogg and Colin P. Williams},
  title = {{Expected Gains from Parallelizing Constraint Solving for Hard Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure