|Publications & Technical Reports|
Anytime AND/OR Depth-ﬁrst Search for Combinatorial OptimizationLars Otten and Rina Dechter
One popular and efﬁcient scheme for solving combinatorial optimization problems over graphical models exactly is depth-ﬁrst Branch and Bound. However, when the algorithm exploits problem decomposition using AND/OR search spaces, its anytime behavior breaks down. This article 1) analyzes and demonstrates this inherent conﬂict between effective exploitation of problem decomposition (through AND/OR search spaces) and the anytime behavior of depth- ﬁrst search (DFS), 2) presents a new search scheme to address this issue while maintaining desirable DFS memory properties, and 3) analyzes and demonstrates its effectiveness through comprehensive empirical evaluation. Our work is applicable to any problem that can be cast as search over an AND/OR search space.