Unconstrained Influence Diagram Solver: Guido

Influence diagrams (ID) are a graphical computational model developed for decision making with uncertainty, based on probability inference. The unconstrained version of this model (UID) drops the restriction of linear ordering of decisions. It adds expressiveness to the model, but it brings an exponential growth of complexity of the already computationally intensive algorithm for optimal ID evaluation. In this article, we present the first application for exact UID solving: Guido. We present the techniques we used to fight the computational complexity and how they affect the performance of the application.