Best-first AND/OR search for 0/1 integer programming

AND/OR search spaces are a unifying paradigm for advanced algorithmic schemes for graphical models. The main virtue of this representation is its sensitivity to the structure of the model, which can translate into exponential time savings for search algorithms. In this paper we introduce an AND/OR search algorithm that explores a context-minimal AND/OR search graph in a best-first manner for solving 0/1 integer linear programs (0/1 ILP). We also extend to the 0/1 ILP domain the depth-first AND/OR branch-and-bound search with caching algorithm which was recently proposed by (R. Marinescu and R. Dechter, 2006) for solving optimization tasks in graphical models. The effectiveness of the best-first AND/OR search approach compared to depth-first AND/OR branch-and-bound search is demonstrated on a variety of benchmarks for 0/1 ILPs, including instances from the MIPLIB library, real-world combinatorial auctions, random uncapacitated warehouse location problems and MAX-SAT instances.Anglai