Solving Multistage Influence Diagrams using Branch-and-Bound Search

Changhe Yuan, Xiaojian Wu, Eric Hansen
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:690-699, 2010.

Abstract

A branch-and-bound approach to solving influ- ence 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 implementa- tion of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solving influence diagrams with multiple stages.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-yuan10a, title = {Solving Multistage Influence Diagrams using Branch-and-Bound Search}, author = {Yuan, Changhe and Wu, Xiaojian and Hansen, Eric}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {690--699}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/yuan10a/yuan10a.pdf}, url = {https://proceedings.mlr.press/r8/yuan10a.html}, abstract = {A branch-and-bound approach to solving influ- ence 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 implementa- tion of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solving influence diagrams with multiple stages.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Solving Multistage Influence Diagrams using Branch-and-Bound Search %A Changhe Yuan %A Xiaojian Wu %A Eric Hansen %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-yuan10a %I PMLR %P 690--699 %U https://proceedings.mlr.press/r8/yuan10a.html %V R8 %X A branch-and-bound approach to solving influ- ence 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 implementa- tion of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solving influence diagrams with multiple stages. %Z Reissued by PMLR on 04 October 2026.
APA
Yuan, C., Wu, X. & Hansen, E.. (2010). Solving Multistage Influence Diagrams using Branch-and-Bound Search. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:690-699 Available from https://proceedings.mlr.press/r8/yuan10a.html. Reissued by PMLR on 04 October 2026.

Related Material