Anytime AND/OR Depth-First Search for Combinatorial Optimization

Authors

  • Lars Otten University of California, Irvine
  • Rina Dechter University of California, Irvine

DOI:

https://doi.org/10.1609/socs.v2i1.18185

Keywords:

search, optimization, anytime, graphical models

Abstract

One popular and efficient scheme for solving exactly combinatorial optimization problems over graphical models is depth-first Branch and Bound. However, when the algorithm exploits problem decomposition using AND/OR search spaces, its anytime behavior breaks down. This paper 1) analyzes and demonstrates this inherent conflict between effective exploitation of problem decomposition (through AND/OR search spaces) and the anytime behavior of depth-first search (DFS), 2) presents a first scheme to address this issue while maintaining desirable DFS memory properties, 3) analyzes and demonstrates its effectiveness. Our work is applicable to any problem that can be cast as search over an AND/OR search space.

Downloads

Published

2021-08-19