IBM Israel Research Seminars

Counting-basedlook-ahead schemes for constraint satisfaction
I will show how belief propagation scheme can approximate counting solutions for CSPs, and can be used to guide value and variable selection heuristics for CSPs.

The impact of AND/OR search space on counting solutions
Contribution
• Introduce AND/OR search spaces, a new framework for graphical models
• showing AND/OR effect on counting solutions

Results
• AND/OR search spaces are always more efficient than traditional OR spaces.
• AND/OR trees are exp(w* log n), while OR trees are exp(n). AND/OR graphs exp(w*), while OR trees are exp(pw*).
• AND/OR search algorithms can flexibly adapt to the amount of available memory, from linear space to exponential in the tree-width
• Constraint propagation techniques are immediately applicable
• The results are equivalent to most current advances (,backjumping, learning (Dechter 1990, Recursive conditioning, Darwiche, Bacchus et. Al. 2003)


Both talks were given in CP2004.