Abstract
This paper presents an extensive empirical evaluation of search algorithms for Constraint Satisfaction Problems (CSPs). By testing combinations of look-back and look-ahead strategies on random binary CSPs and structured chain models, the authors identify Conflict-Directed Backjumping (BJ) paired with Dynamic Variable Ordering (DVO) as the most robust and efficient approach. The study also clarifies the role of Forward Checking and introduces the "Sticking Values" heuristic, demonstrating that memory-based enhancements can significantly reduce search time.
Introduction
Constraint Satisfaction Problems (CSPs), such as scheduling and resource allocation, are fundamental to artificial intelligence but remain NP-complete. In the early 1990s, numerous search algorithms were proposed, yet their relative performance in average-case scenarios was poorly understood. Daniel Frost and Rina Dechter (1994) addressed this gap by conducting a massive empirical "bake-off" to determine which combinations of look-back (backjumping, backmarking) and look-ahead (forward checking, variable ordering) strategies dominate in practice, particularly near the "phase transition" where problems are most difficult to solve.
Experimental Framework
The authors evaluated several core algorithms and heuristics:
- Algorithms: Backtracking (BT), Conflict-Directed Backjumping (BJ), and Backmarking (BM).
- Variable Ordering: Static Min-width (MW) ordering versus Dynamic Variable Ordering (DVO), which selects the variable with the smallest remaining domain at each step.
- Value Ordering: The introduction of Sticking Values (SV), a heuristic that prioritizes the last successful value assigned to a variable.
Experiments utilized two problem generators: Random Binary CSPs defined by parameters $N$ (variables), $K$ (domain size), $T$ (tightness), and $C$ (constraints), and a structured "Chain Model" designed to mimic real-world architectural features.
The Dominance of BJ + DVO
The most significant finding of the study was the powerful synergy between Backjumping and Dynamic Variable Ordering. While BJ excels on sparse, structured graphs by jumping over irrelevant variables during retreats, DVO thrives on denser graphs by pruning the search space early. Together, they provide a robust solution across a wide range of problem types.
As shown in the experimental data, the BJ+DVO combination often outperforms other configurations by orders of magnitude on large, hard instances. For example, in problems with $N=100$ and $T=1/9$, BJ+DVO reduced the number of consistency checks from over 320 million (with BJ+MW) to under 200,000.
The Role of Memory and Heuristics
The study also explored the benefits of adding "memory" to the search process. By integrating Backmarking (BM) and the Sticking Values (ST) heuristic with Backjumping, the authors observed substantial efficiency gains. Sticking Values proved that simply trying the "last known good" value can significantly accelerate the search, especially when domain sizes are small.
Integrating these techniques typically reduced CPU time by 50% to 66%. On structured chain problems, the combination of BJ and DVO was over ten times faster than using either technique in isolation, highlighting the importance of algorithm selection for non-random problem structures.
Re-evaluating Forward Checking
A surprising insight from the paper concerns Forward Checking (FC), which was long considered a premier algorithm. The authors demonstrated that when DVO is employed, the performance of simple Backtracking is nearly identical to that of Forward Checking. This suggests that FC’s legendary efficiency is primarily derived from the "fail-first" variable ordering it implicitly facilitates, rather than the forward checking mechanism itself.
Conclusion
Frost and Dechter’s work established BJ+DVO as a foundational standard for CSP search. Their findings emphasize that the hardest problems at the phase transition—particularly those with many "loose" constraints—require a sophisticated combination of look-ahead pruning and look-back jumping. Furthermore, the success of the Sticking Values heuristic suggests that even simple memory-based heuristics can provide significant performance boosts in practical applications.
Summary updated