Caching in Context-Minimal OR Spaces

In empirical studies we observed that caching can have very little impact in reducing the search effort in Branch and Bound search over context-minimal OR spaces. For example, in one of the problem domains used in our experiments we reduce only by 1% the number of nodes expanded when using caching in context-minimal OR spaces. By contrast, we reduce by 74% the number of nodes expanded when using caching in context-minimal AND/OR spaces on the same instances. In this work we document this unexpected empirical finding and provide explanations for the phenomenon.

Authors

• Rina Dechter
• Levi H. S. Lelis
• Lars Otten

Keywords

• branch and bound
• subproblem caching
• optimization
• graphical models