AND/OR Tree Search for Constraint Optimization
Radu Marinescu, Rina Dechter · 2004
The paper presents and evaluates the power of a new framework for constraint optimization, based on the concept of AND/OR search trees. The virtue of the AND/OR search tree representation is that its size may be smaller than that of a traditional OR search tree. We introduce a new generation of depth first Branch-and-Bound algorithms that traverse an AND/OR search space and use the Mini-Bucket approximation scheme to generate heuristics to guide the search. Our