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 gen- eralized to solve LIMIDs, however, and only re- cently 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 re- lated to the approach of solving an influence di- agram by converting it to an equivalent decision tree, with the difference that the LIMID is con- verted 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 gen- eralized to solve LIMIDs, however, and only re- cently 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 re- lated to the approach of solving an influence di- agram by converting it to an equivalent decision tree, with the difference that the LIMID is con- verted 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 gen- eralized to solve LIMIDs, however, and only re- cently 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 re- lated to the approach of solving an influence di- agram by converting it to an equivalent decision tree, with the difference that the LIMID is con- verted 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