Caching in Context-Minimal OR Spaces
DOI:
https://doi.org/10.1609/socs.v6i1.18381Keywords:
branch and bound, subproblem caching, optimization, graphical modelsAbstract
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.
Downloads
Published
2021-09-01
Issue
Section
Short Papers