Caching in Context-Minimal OR Spaces

Proceedings of the International Symposium on Combinatorial Search, 8

Volume

Vol. 8 No. 1 (2015): Eighth Annual Symposium on Combinatorial Search

Short Papers

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.

10.1609/socs.v6i1.18381