Mathematical programming for influence diagrams

Influence Diagrams 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 an influence diagram, 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. We present a mixed integer linear formulation for solving an influence diagram, 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 heuristic algorithm for addressing influence diagrams.