×

zbMATH — the first resource for mathematics

Memory intensive AND/OR search for combinatorial optimization in graphical models. (English) Zbl 1185.68649
Summary: We explore the impact of caching during search in the context of the recent framework of AND/OR search in graphical models. Specifically, we extend the depth-first AND/OR Branch-and-Bound tree search algorithm to explore an AND/OR search graph by equipping it with an adaptive caching scheme similar to good and no-good recording. Furthermore, we present best-first search algorithms for traversing the same underlying AND/OR search graph and compare both algorithms empirically. We focus on two common optimization problems in graphical models: finding the Most Probable Explanation in belief networks and solving Weighted CSPs. In an extensive empirical evaluation, we demonstrate conclusively the superiority of the memory intensive AND/OR search algorithms on a variety of benchmarks.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Software:
Chaff
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Marinescu, R.; Dechter, R., AND/OR branch-and-bound search for combinatorial optimization in graphical models, Artificial intelligence, 173, 16-17, 1457-1491, (2009), this issue · Zbl 1185.68648
[2] R. Marinescu, R. Dechter, AND/OR branch-and-bound for graphical models, in: International Joint Conference on Artificial Intelligence (IJCAI), 2005, pp. 224-229
[3] R. Marinescu, R. Dechter, Dynamic orderings for AND/OR branch-and-bound search in graphical models, in: European Conference on Artificial Intelligence (ECAI), 2006, pp. 138-142
[4] Dechter, R., Enhancement schemes for constraint processing: backjumping, learning and cutset decomposition, Artificial intelligence, 41, 3, 273-312, (1990)
[5] R. Bayardo, D. Miranker, On the space-time trade-off in solving constraint satisfaction problems, in: International Joint Conference on Artificial Intelligence (IJCAI), 1995, pp. 558-562
[6] Darwiche, A., Recursive conditioning, Artificial intelligence, 126, 1-2, 5-41, (2001) · Zbl 0969.68150
[7] F. Bacchus, S. Dalmao, T. Pittasi, Value elimination: Bayesian inference via backtracking search, in: Uncertainty in Artificial Intelligence (UAI), 2003, pp. 20-28
[8] P. Jegou, C. Terrioux, Decomposition and good recording for solving Max-CSPs, in: European Conference on Artificial Intelligence (ECAI), 2004, pp. 196-200
[9] Dechter, R.; Pearl, J., Generalized best-first search strategies and the optimality of \(\operatorname{A}^\ast\), Journal of the ACM, 32, 3, 505-536, (1985) · Zbl 0631.68075
[10] Kask, K.; Dechter, R., A general scheme for automatic generation of search heuristics from specification dependencies, Artificial intelligence, 129, 1-2, 91-131, (2001) · Zbl 0971.68035
[11] Dechter, R.; Rish, I., Mini-buckets: A general scheme for approximating inference, Journal of the ACM, 50, 2, 107-153, (2003) · Zbl 1326.68335
[12] Pearl, J., Probabilistic reasoning in intelligent systems, (1988), Morgan Kaufmann
[13] Bistarelli, S.; Montanari, U.; Rossi, F., Semiring based constraint solving and optimization, Journal of the ACM, 44, 2, 309-315, (1997)
[14] R. Marinescu, R. Dechter, Memory intensive branch-and-bound search for graphical models, in: National Conference on Artificial Intelligence (AAAI), 2006 · Zbl 1177.90292
[15] R. Marinescu, R. Dechter, Best-first AND/OR search for graphical models, in: National Conference on Artificial Intelligence (AAAI), 2007, pp. 1171-1176 · Zbl 1214.90088
[16] R. Marinescu, R. Dechter, Best-first AND/OR search for most probable explanations, in: Uncertainty in Artificial Intelligence (UAI), 2007 · Zbl 1214.90088
[17] Kask, K.; Dechter, R.; Larrosa, J.; Dechter, A., Unifying cluster-tree decompositions for reasoning in graphical models, Artificial intelligence, 166, 1-2, 165-193, (2005) · Zbl 1132.68680
[18] Dechter, R.; Mateescu, R., AND/OR search spaces for graphical models, Artificial intelligence, 171, 1, 73-106, (2007) · Zbl 1168.68549
[19] Nilsson, N.J., Principles of artificial intelligence, (1980), Tioga · Zbl 0422.68039
[20] E. Freuder, M. Quinn, Taking advantage of stable sets of variables in constraint satisfaction problems, in: International Joint Conference on Artificial Intelligence (IJCAI), 1985, pp. 1076-1078
[21] Pearl, J., Heuristics: intelligent search strategies for computer problem solving, (1984), Addison-Wesley
[22] Kanal, L.; Kumar, V., Search in artificial intelligence, (1988), Springer-Verlag · Zbl 0648.68104
[23] R. Mateescu, R. Dechter, AND/OR cutset conditioning, in: International Joint Conference on Artificial Intelligence (IJCAI), 2005, pp. 230-235
[24] A. Martelli, U. Montanari, Additive AND/OR graphs, in: International Joint Conference on Artificial Intelligence (IJCAI), 1973, pp. 1-11
[25] Dechter, R., Bucket elimination: A unifying framework for reasoning, Artificial intelligence, 113, 1-2, 41-85, (1999) · Zbl 0939.68847
[26] R. Marinescu, AND/OR search strategies for combinatorial optimization in graphical models, PhD thesis, University of California, Irvine, 2008
[27] R. Marinescu, R. Dechter, Memory intensive AND/OR search for combinatorial optimization in graphical models, Technical report, University of California, Irvine, 2008 · Zbl 1185.68649
[28] S. de Givry, F. Heras, J. Larrosa, M. Zytnicki, Existential arc consistency: Getting closer to full arc consistency in weighted CSPs, in: International Joint Conference in Artificial Intelligence (IJCAI), 2005, pp. 84-89
[29] S. de Givry, T. Schiex, G. Verfaillie, Exploiting tree decomposition and soft local consistency in weighted CSP, in: National Conference on Artificial Intelligence (AAAI), 2006
[30] T. Sang, P. Beame, H. Kautz, Solving Bayesian networks by weighted model counting, in: National Conference of Artificial Intelligence (AAAI), 2005, pp. 475-482
[31] Ott, J., Analysis of human genetic linkage, (1999), The Johns Hopkins University Press
[32] M. Fishelson, D. Geiger, Exact genetic linkage computations for general pedigrees, in: International Conference on Intelligent Systems for Molecular Biology (ISMB), 2002, pp. 189-198
[33] Fishelson, M.; Dovgolevsky, N.; Geiger, D., Maximum likelihood haplotyping for general pedigrees, Human heredity, 59, 1, 41-60, (2005)
[34] J. Park, Using weighted Max-SAT engines to solve MPE, in: National Conference of Artificial Intelligence (AAAI), 2002, pp. 682-687
[35] F. Hutter, H. Hoos, T. Stutzle, Efficient stochastic local search for MPE solving, in: International Joint Conference on Artificial Intelligence (IJCAI), 2005, pp. 169-174
[36] C. Voudouris, Guided local search for combinatorial optimization problems. Technical report, PhD thesis, University of Essex, 1997 · Zbl 0882.90102
[37] Mills, P.; Tsang, E., Guided local search for solving SAT and weighted MAX-SAT problems, Journal of automated reasoning (JAR), 24, 1-2, 205-223, (2000) · Zbl 0967.68152
[38] R. Dechter, D. Larkin, Hybrid processing of beliefs and constraints, in: Uncertainty in Artificial Intelligence (UAI), 2001, pp. 112-119
[39] D. Larkin, R. Dechter, Bayesian inference in the presence of determinism, in: Artificial Intelligence and Statistics (AISTAT), 2003
[40] D. Allen, A. Darwiche, New advances in inference using recursive conditioning, in: Uncertainty in Artificial Intelligence (UAI), 2003, pp. 2-10
[41] R. Dechter, R. Mateescu, Mixtures of deterministic-probabilistic networks, in: Uncertainty in Artificial Intelligence (UAI), 2004, pp. 120-129
[42] Rish, I.; Dechter, R., Resolution vs. search: two strategies for SAT, Journal of automated reasoning, 24, 1-2, 225-275, (2000) · Zbl 0967.68147
[43] T. Walsh, SAT vs CSP, in: Principles and Practice of Constraint Programming (CP), 2000, pp. 441-456 · Zbl 1044.68808
[44] M. Moskewicz, C. Madigan, Y. Zhao, L. Zhang, S. Malik, Chaff: Engineering an efficient SAT solver, in: Design Automation Conference (DAC), 2001
[45] Bensana, E.; Lemaitre, M.; Verfaillie, G., Earth observation satellite management, Constraints, 4, 3, 293-299, (1999) · Zbl 0963.90507
[46] Chavira, M.; Darwiche, A.; Jaeger, M., Compiling relational Bayesian networks for exact inference, International journal of approximate reasoning, 42, 1-2, 4-20, (2006) · Zbl 1096.68747
[47] Chakrabati, P.; Ghose, S.; Acharya, A.; de Sarkar, S., Heuristic search in restricted memory, Artificial intelligence, 41, 2, 197-221, (1989) · Zbl 0687.68040
[48] Korf, R., Linear-space best-first search, Artificial intelligence, 62, 1, 41-78, (1993) · Zbl 0778.68079
[49] R. Zhou, E. Hansen, Structured duplicate detection in external-memory graph search, in: National Conference on Artificial Intelligence (AAAI-04), 2004, pp. 683-689
[50] R. Zhou, E. Hansen, External-memory pattern databases using structured duplicate detection, in: National Conference on Artificial Intelligence (AAAI-05), 2005, pp. 1398-1405
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.