Best-first AND/OR search for 0/1 integer programming
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Marinescu, R., & Dechter, R. (2007). Best-first AND/OR search for 0/1 integer programming. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 171-185). Springer-verlag. https://hdl.handle.net/2078.5/221785