Solving Multistage Influence Diagrams using Branch-and-Bound Search

Changhe Yuan, Xiaojian Wu, Eric Hansen


A branch-and-bound approach to solving influence diagrams has been previously proposed in the literature, but appears to have never been implemented and evaluated -- apparently due to the difficulties of computing effective bounds for the branch-and-bound search. In this paper, we describe how to efficiently compute effective bounds, and we develop a practical implementation of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solving influence diagrams with multiple stages.



author = {Changhe Yuan and Xiaojian Wu and Eric Hansen},
title = {Solving Multistage Influence Diagrams using Branch-and-Bound Search},
booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI-10)},
year = {2010},
pages = {691--700},
address = {Catalina Island, CA}