Sparse Constraint Graphs and Exceptionally Hard Problems

IJCAI 1995

TL;DR

This paper investigates "exceptionally hard problems" (EHPs) in binary constraint satisfaction problems (CSPs). It reveals that these rare, but incredibly difficult, instances are far more likely to occur in sparse constraint graphs and can be significantly mitigated by using conflict-directed backjumping (CBJ) instead of standard chronological backtracking.

What Problem Does This Paper Address?

Many computational problems exhibit a "phase transition" as a parameter is varied. This transition marks a shift from a region where most problems are easily solvable to one where most are easily proven insoluble. In between lies the "mushy region," where problems are generally hard. However, this paper focuses on a peculiar phenomenon: "exceptionally hard problems" (EHPs). These are individual problems that are orders of magnitude harder than almost all others, even those in the "easy and soluble" region, and are often harder than problems in the mushy region itself. The authors aim to understand where these EHPs occur, what causes them, and if they can be avoided, particularly in the context of binary CSPs.

Methods

The core of the research involves generating large populations of random binary CSPs and solving them using different search algorithms.

  • Random CSP Generation: Problems are characterized by:
  • n: number of variables

    • m: number of values per variable
    • p₁: constraint density (proportion of variable pairs with constraints)
    • p₂: constraint tightness (proportion of value pairs forbidden by a constraint) The phase transition is typically observed by varying p₂ while keeping n, m, and p₁ fixed.
  • Search Algorithms:

    • Forward Checking (FC) with Fail-First Heuristic: This is the baseline algorithm. It uses forward checking to prune the search space and the fail-first heuristic to select the most constrained variable with the fewest remaining values.
  • Conflict-Directed Backjumping (CBJ): This is an informed backtracking technique. When a conflict is detected, CBJ jumps back to the specific variable that caused the conflict, rather than just the immediately preceding one, as chronological backtracking does.
  • FC-CBJ-FF: This combines forward checking, the fail-first heuristic, and conflict-directed backjumping.
  • Measurement: The "cost" of solving a problem is measured by the number of consistency checks performed.

Datasets

The paper does not introduce new benchmark datasets. Instead, it relies on randomly generated binary CSP instances, varying parameters like constraint density (p₁) and tightness (p₂) to explore different regions of the problem space. The authors generated up to 50,000 problems for specific parameter sets to ensure a statistically significant chance of observing rare EHPs.

Key Insights and Ideas

  • Sparse is Harder (for EHPs): EHPs are overwhelmingly found in problems with sparse constraint graphs (low p₁). In dense problems, even with large sample sizes, no EHPs were observed. This suggests that the structure of the constraint graph plays a crucial role in the emergence of these difficult instances.
  • EHPs are "Early Failure" Problems: The analysis of EHPs reveals that they often occur when the search algorithm makes a few initial variable assignments that lead to a hard, insoluble subproblem. The exceptional difficulty arises from the extensive effort required to prove this subproblem insoluble, even though the overall problem might be soluble.
  • CBJ is a Targeted Solution: Conflict-directed backjumping (CBJ) significantly reduces the difficulty of EHPs. By jumping directly to the source of a conflict, it avoids the extensive search within the insoluble subproblem that plagues chronological backtracking.
  • Fail-First Matters: While CBJ is beneficial, its impact is most pronounced when combined with the fail-first heuristic. This suggests that the initial variable ordering is critical in guiding the search towards the problematic subproblems that CBJ can then efficiently handle.
  • EHPs are Algorithm-Dependent: The paper highlights that what constitutes an EHP is dependent on the search algorithm used. A minor change in variable instantiation order can turn an EHP into a much easier problem.

Key Results

  • Sparse CSPs (e.g., n=20, m=10, p₁=0.2) exhibit EHPs: In these cases, the maximum cost can be two orders of magnitude higher than the median cost.
  • Dense CSPs (e.g., p₁=1.0) show little variation in difficulty: Even with up to 50,000 problems, no EHPs were found.
  • CBJ dramatically reduces EHP difficulty: For specific EHPs, FC-CBJ-FF required significantly fewer consistency checks (e.g., 3 million vs. 376 million for one problem) compared to FC-FF.
  • CBJ's benefit is concentrated on EHPs: For most problems, especially in dense CSPs, the performance difference between FC-FF and FC-CBJ-FF is minimal. The significant savings are primarily seen on the hardest instances.

Limitations and Future Work

  • Randomness: All experiments are based on randomly generated CSPs. The authors acknowledge that problems with more structured constraint graphs, varying domain sizes, or different constraint tightness distributions might behave differently.
  • Definition of EHP: The definition of an EHP is qualitative ("much more difficult, by at least an order of magnitude"). While useful, a more precise mathematical definition could be explored.
  • Algorithm Dependence: The paper emphasizes that EHPs are algorithm-dependent. Future work could explore other search algorithms and heuristics to see how they interact with EHPs.
  • Avoiding EHPs: While CBJ mitigates EHPs, it doesn't eliminate them entirely. The question of whether any algorithm can completely avoid EHPs in sparse CSPs remains open.
  • Double Peaks: The authors note that their graphs don't show the "double peak" in higher percentiles observed in some other studies (e.g., on graph coloring problems). They suggest this might be due to smaller sample sizes compared to those studies, and that larger samples might reveal this phenomenon.

Summary updated

BibTeX
@inproceedings{1995sparse,
  title = {{Sparse Constraint Graphs and Exceptionally Hard Problems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure