Improved Limited Discrepancy Search

AAAI 1996

TL;DR

This paper introduces an improved version of Limited Discrepancy Search (LDS), an algorithm for finding optimal solutions in large search spaces. The new algorithm, ILDS, significantly reduces redundant computations compared to its predecessor, making it a more practical alternative to traditional depth-first search when exhaustive exploration is infeasible.

What Problem Does This Paper Address?

When searching through vast problem spaces, like those encountered in optimization or constraint satisfaction, it's often impossible to explore every possible path to find the best solution. Traditional methods like breadth-first search are too memory-intensive, while depth-first search can be inefficient if the optimal solution lies down a path that isn't explored early. Limited Discrepancy Search (LDS) offers a middle ground by prioritizing paths with fewer "discrepancies" (deviations from a preferred branch). However, the original LDS algorithm (OLDS) suffered from significant redundancy, re-exploring many paths across different iterations. This paper addresses the inefficiency of OLDS by proposing a more streamlined approach that guarantees each leaf node is visited only once.

Methods

The core contribution is an improved algorithm called Improved Limited Discrepancy Search (ILDS). The key innovation lies in how it generates paths. While the original LDS (OLDS) generated all paths with at most k discrepancies in iteration k, ILDS generates paths with exactly k discrepancies. This is achieved by carefully tracking the remaining depth to be searched and adjusting the search strategy when the remaining depth is less than or equal to the allowed discrepancies. This ensures that each leaf node at the maximum search depth is generated precisely once, corresponding to the number of discrepancies in its path from the root. The paper also analyzes the overhead of ILDS compared to depth-first search (DFS), showing that for a complete b-ary tree, the overhead is a factor of $b/(b-1)$.

Datasets

The paper uses the number partitioning problem as a benchmark. Specifically, they evaluate their algorithms on:

  • Random ten-digit integers uniformly distributed from zero to 10 billion, with problem sizes ranging from 5 to 100 values.
  • Random eight-digit integers uniformly distributed from zero to 100 million, using a simpler partitioning algorithm.

Key Insights and Ideas

  • Eliminating Redundancy: The primary insight is that by generating paths with exactly k discrepancies, ILDS avoids the significant re-computation inherent in OLDS, where paths with fewer than k discrepancies are revisited in iteration k.
  • Trade-off between Diligence and Dilettantism: The paper highlights that LDS, in general, can be seen as "dilettantish" (exploring many different paths broadly), while DFS is "diligent" (deeply pursuing a single path). The effectiveness of each depends on the problem's structure and the quality of the heuristic guiding the search.
  • Heuristic Quality Matters: The performance of LDS relative to DFS is strongly influenced by the quality of the heuristic used to order branches. A stronger heuristic leads to better performance for LDS.
  • Pruning's Impact: While ILDS's theoretical overhead over DFS is small for complete trees, real-world pruning (where branches terminate before maximum depth) can increase ILDS's overhead relative to DFS.

Key Results

  • Asymptotic Complexity: ILDS reduces the asymptotic complexity for complete binary trees from $O(b^{2d})$ to $O(b^d)$, where $b$ is the branching factor and $d$ is the depth.
  • Empirical Performance (CKK Algorithm): On the Complete Karmarkar-Karp (CKK) algorithm for number partitioning, ILDS consistently outperforms OLDS. For problems where perfect partitions are rare (left side of the peak difficulty), DFS is the best choice. For problems with many perfect partitions (right side of the peak), ILDS and OLDS outperform DFS, with the gap narrowing as problem size increases. ILDS showed a measured node generation ratio of approximately 3.5x DFS on binary trees in experiments.
  • Empirical Performance (Simpler Algorithm): On a simpler number partitioning algorithm, DFS consistently outperformed ILDS, even for problems with perfect partitions. This is attributed to the weaker heuristic in this simpler algorithm, making LDS's "dilettantism" a disadvantage.

Limitations and Future Work

  • Interior Node Overhead: While ILDS generates each leaf node exactly once, it still generates interior nodes multiple times. This overhead increases with pruning.
  • Heuristic Dependence: The effectiveness of LDS is highly dependent on the quality of the heuristic used to order branches. A weak heuristic can lead to worse performance than DFS.
  • Problem Specificity: The paper concludes that no single algorithm is ideal for all problems. The optimal choice depends on finding a balance between diligence (DFS) and dilettantism (LDS), which is problem-specific.
  • Future Work: The paper suggests that further research could explore algorithms that strike a better balance between diligence and dilettantism. The authors also mention that their improved LDS algorithm is a viable alternative to DFS when exhaustive search is not possible, especially when combined with strong heuristics.

Summary updated

BibTeX
@inproceedings{1996improved,
  title = {{Improved Limited Discrepancy Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure