  Influence Diagrams (ID) are a flexible tool to represent discrete stochastic
optimization problems, including Markov Decision Process (MDP) and Partially
Observable MDP as standard examples. More precisely, given random variables
considered as vertices of an acyclic digraph, a probabilistic graphical model
defines a joint distribution via the conditional distributions of vertices
given their parents. In ID, the random variables are represented by a
probabilistic graphical model whose vertices are partitioned into three types :
chance, decision and utility vertices. The user chooses the distribution of the
decision vertices conditionally to their parents in order to maximize the
expected utility. Leveraging the notion of rooted junction tree, we present a
mixed integer linear formulation for solving an ID, as well as valid
inequalities, which lead to a computationally efficient algorithm. We also show
that the linear relaxation yields an optimal integer solution for instances
that can be solved by the "single policy update", the default algorithm for
addressing IDs.
