TL;DR
This paper introduces the Cross Product Representation (CPR), a method for grouping partial solutions in Constraint Satisfaction Problems (CSPs) into sets rather than individual tuples. By representing search subspaces as Cartesian products of value sets, the authors transform the computational complexity of consistency testing from multiplicative to additive, leading to speedups of up to three orders of magnitude.
What Problem Does This Paper Address?
In AI search, researchers often encounter the "battle of the bulge." When solving a CSP—like scheduling, vision, or planning—you start with a few variables and many possible values. As you progress, the number of "partial solutions" (combinations of values that work so far) explodes before eventually narrowing down to a few final solutions.
Standard backtracking algorithms test every new variable against every single existing partial solution individually. This is computationally expensive because the number of combinations grows exponentially. The authors sought a way to represent these "bulges" of partial solutions more compactly so that new values could be tested against entire groups of solutions at once.
Methods
The core innovation is CPR (Cross Product Representation).
Instead of storing partial solutions as a list of individual pairs like {(a, d), (a, e), (b, d), (b, e)}, CPR represents them as a cross product of sets: {a, b} x {d, e}.
Key Algorithmic Changes:
- Additive Complexity: If you have a new value $g$ for variable $Z$, and you want to check it against a cross product $\{a, b, c\} \times \{d, e, f\}$, standard search requires $3 \times 3 = 9$ tests. With CPR, you only need $3 + 3 = 6$ tests (checking $g$ against the first set, then the second).
- BT-CPR: The authors modified the standard Backtracking (BT) algorithm to include a "generate and merge" step. As the search tree grows, the algorithm looks for "sibling" nodes that are identical except for the current variable's value and merges them into a single cross-product set.
- FC-CPR: The paper also outlines how this can be applied to Forward Checking (FC), where the algorithm "looks ahead" to prune future domains.
Datasets
The authors evaluated their approach using a random binary CSP generator.
- Variables: 10 variables per problem.
- Parameters: They varied three main factors:
- Constraint Density: How many pairs of variables are constrained (0 to 1).
- Constraint Tightness: What fraction of value pairs are forbidden (0 to 1).
- Domain Size: The number of possible values per variable (expected value of 5).
- Scale: They tested 15 combinations of tightness and density, with five problems per combination.
Key Insights and Ideas
- The "No-Harm" Guarantee: The authors prove (Theorem 1) that BT-CPR will never require more constraint checks than standard backtracking when looking for all solutions. In the worst case, it simply defaults to standard backtracking.
- Efficiency in Weakly Constrained Spaces: CPR shines most in "weakly constrained" problems—those where many combinations are allowed. These are traditionally "hard" because the search space doesn't prune quickly; CPR tames this by collapsing the space.
- Batched Solutions: Because CPR represents sets of solutions, the algorithm can return solutions in "batches" (e.g., finding a cross product that represents 15 solutions at once).
- Frustrating Problems: The authors highlight that CPR is excellent for "frustrating" problems where many paths almost work but fail at the very end. CPR processes these failures much faster by failing entire sets of partial solutions simultaneously.
Key Results
- Massive Speedups: In weakly constrained problems, BT-CPR outperformed standard backtracking by three orders of magnitude.
- Real-world Time Savings: In one extreme case, standard backtracking took 13,986 seconds (nearly 4 hours) and 77 million checks, while BT-CPR finished in just 3.21 seconds and 25,000 checks.
- Low Overhead: The "checks per second" ratio remained close to 1, meaning the computational cost of managing the cross-product sets is negligible compared to the savings in constraint checks.
- Better than Forward Checking: Even the basic BT-CPR was found to be more efficient than standard Forward Checking (a more advanced traditional algorithm) for certain weakly constrained problems.
Limitations and Future Work
- Implementation Status: While the theory for Forward Checking with CPR (FC-CPR) is provided, the paper notes it had not been fully implemented at the time of publication.
- Heuristic Ordering: The authors mention a "catch-22" regarding variable ordering. Standard CSP heuristics (like "fail first") try to narrow the search tree quickly, but CPR thrives when there are many possibilities to group together. They suggest that the "opposite" of standard heuristics might actually work better for CPR.
- Search Type: The current implementation is depth-first. The authors suggest that a breadth-first approach might offer even more opportunities for merging "cousin" nodes across the tree, though it would incur higher memory overhead.
Summary updated