Approximate Resolution of Hard Numbering Problems

AAAI 1996

TL;DR

This paper introduces a novel stochastic method for estimating the number of solutions to Constraint Satisfaction Problems (CSPs), particularly focusing on hard problems like SAT and the N-Queens problem. By sampling paths in a search tree rather than exhaustively exploring it, the authors provide a way to get both unbiased estimates and provable lower bounds on the solution count, offering a practical alternative to computationally intractable exact methods.

What Problem Does This Paper Address?

Many real-world problems can be modeled as Constraint Satisfaction Problems (CSPs). Deciding if a CSP has any solution is often hard (NP-complete), but counting the number of solutions is even harder (#P-complete). For many complex CSP instances, finding the exact number of solutions is computationally infeasible, even with sophisticated algorithms. This paper tackles the challenge of estimating this number when exact counting is impossible, aiming to provide useful approximations and bounds that can inform problem analysis and algorithm development.

Methods

The core of the paper's contribution lies in a stochastic forward-checking algorithm. Instead of a traditional forward-checking algorithm that explores the entire search tree to count solutions, this new method uses a probabilistic approach. It works by:

  1. Stochastic Forward Checking: The algorithm explores a search tree but, at each internal node, it doesn't branch on all possible variable assignments. Instead, it probabilistically chooses a path to follow down the tree. This is achieved by drawing a path from the root to a leaf, where each step involves uniformly choosing a child node.
  2. Estimating Solution Count: For each sampled path, the algorithm calculates a value related to the number of solutions associated with that path. By averaging these values over many sampled paths, an unbiased estimate of the total number of solutions can be obtained.
  3. Lower Bound Guarantee: A key theoretical result is a proposition that allows for the computation of a lower bound on the number of solutions with a guaranteed error probability. This is achieved by taking the minimum of several independent estimates.

The method leverages the "forward checking" algorithm, a standard technique in CSP solving, but adapts it for probabilistic sampling.

Datasets

The paper evaluates its method on two types of problems:

  • Boolean Satisfiability (SAT) instances:
    • Random 3-SAT instances: Generated with 50 variables and varying numbers of clauses (around 60 and 100).
  • Structured SAT instances: Specifically, instances derived from graph coloring problems (Btree(n)) and Ramsey theory problems (Ramsey(n)). These were chosen because their exact solution counts are computable, allowing for direct comparison.
  • N-Queens problem instances: Used to demonstrate the method's applicability to another classic CSP.

The authors note that for some instances (e.g., 100-clause 3-SAT), exact counting is difficult, making their estimation method particularly valuable.

Key Insights and Ideas

  • Sampling Paths is Efficient: The paper demonstrates that by sampling paths in the search tree, one can obtain reasonable estimates of the solution count without the prohibitive cost of full exploration. This is especially true for hard instances where the search space is vast.
  • Provable Lower Bounds: The ability to provide a lower bound with a controlled error probability is a significant theoretical contribution. This offers a level of confidence in the estimate, even if an exact number isn't available.
  • Heuristic Impact: The choice of heuristics (e.g., choosing variables from smaller clauses) can significantly improve the probability of finding solutions via sampled paths, making the estimates more accurate and efficient.
  • Estimating Search Tree Size: The method can also be used to estimate the size of the search tree itself, which is useful for evaluating the performance of different algorithms and heuristics without full exploration.

Key Results

  • Good Estimates for 3-SAT: For random 3-SAT instances with 50 variables and 100 clauses, estimates obtained from sampling 1000 paths (about 1.5% of internal nodes) showed good correlation with the exact number of solutions, with points clustering around the diagonal line.
  • Effective for Structured Problems: The method provided accurate estimates for structured SAT instances (Btree and Ramsey) and the N-Queens problem, often with low relative standard deviations (e.g., 5.8% for Btree(4), 3.8% for Ramsey(7)).
  • Lower Bounds for N-Queens: For N-Queens instances where exact counting is challenging, the paper provided lower bounds with very low error probabilities (e.g., < 10⁻³⁰).

Limitations and Future Work

  • No Reliable Upper Bound: The authors acknowledge that they do not currently know how to compute a reliable upper bound for the number of solutions.
  • Dependence on Heuristics: The quality of estimates is dependent on the chosen heuristics for variable selection and path sampling.
  • Future Work: The paper suggests exploring methods for computing upper bounds and further investigating the impact of different heuristics and sampling strategies. They also propose using this estimation technique to evaluate the time needed to compute exact solutions for problem instances.

Summary updated

BibTeX
@inproceedings{1996approximate,
  title = {{Approximate Resolution of Hard Numbering Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure