Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search

Arindam Khaled, Changhe Yuan, Eric Hansen
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:471-480, 2013.

Abstract

A limited-memory influence diagram (LIMID) generalizes a traditional influence diagram by relaxing the assumptions of regularity and no-forgetting, allowing a wider range of decision problems to be modeled. Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this paper, we introduce an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-khaled13a, title = {Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search}, author = {Khaled, Arindam and Yuan, Changhe and Hansen, Eric}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {471--480}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/khaled13a/khaled13a.pdf}, url = {https://proceedings.mlr.press/r11/khaled13a.html}, abstract = {A limited-memory influence diagram (LIMID) generalizes a traditional influence diagram by relaxing the assumptions of regularity and no-forgetting, allowing a wider range of decision problems to be modeled. Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this paper, we introduce an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search %A Arindam Khaled %A Changhe Yuan %A Eric Hansen %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-khaled13a %I PMLR %P 471--480 %U https://proceedings.mlr.press/r11/khaled13a.html %V R11 %X A limited-memory influence diagram (LIMID) generalizes a traditional influence diagram by relaxing the assumptions of regularity and no-forgetting, allowing a wider range of decision problems to be modeled. Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this paper, we introduce an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently. %Z Reissued by PMLR on 04 October 2026.
APA
Khaled, A., Yuan, C. & Hansen, E.. (2013). Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:471-480 Available from https://proceedings.mlr.press/r11/khaled13a.html. Reissued by PMLR on 04 October 2026.

Related Material