Caching in Context-Minimal OR Spaces

Authors

  • Rina Dechter University of California, Irvine
  • Levi Lelis Universidade Federal de Viçosa
  • Lars Otten University of California, Irvine

DOI:

https://doi.org/10.1609/socs.v6i1.18381

Keywords:

branch and bound, subproblem caching, optimization, graphical models

Abstract

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