Computational Complexity

Introduction

Decision programming relies on mixed-integer linear programming, which is known to be an NP-complete problem. In this section, we analyze how the influence diagram affects the size of the mixed-integer linear model, determining whether it is tractable.

We use the following inequalities for sum and product of non-negative elements $A$ to derive the lower and upper bounds for the number of paths and the number of decision stages. Sum inequality:

\[|A| \left(\min_{a∈A} a\right) ≤ ∑_{a∈A} a ≤ |A| \left(\max_{a∈A} a\right).\]

Product inequality:

\[\left(\min_{a∈A} a\right)^{|A|} ≤ ∏_{a∈A} a ≤ \left(\max_{a∈A} a\right)^{|A|}.\]

The following bounds for the number of paths and the number of decision stages show how the number of states, nodes, and arcs affects the size of the model.

Number of Paths

We define the number of paths as

\[|𝐒|=∏_{i∈C∪D} |S_i|.\]

From the definition of the influence diagram, we have the path length of $n=|C∪D|.$ Then, we have the bounds for the number of paths as

\[\left(\min_{i∈C∪D} |S_i|\right)^n ≤ |𝐒| ≤ \left(\max_{i∈C∪D} |S_i|\right)^n.\]

We assume non-trivial influence diagram such that $|S_i|≥2$ for all $i∈C∪D$. That is, each decision or chance node has at least two states. Therefore, the number of paths is always exponential to the path length of $n.$

Number of Decision Stages

We define the number of decision stages as

\[∑_{i∈D}|𝐒_{I(i)}| |S_i| = ∑_{i∈D} |S_i| ∏_{j∈I(i)}|S_j| = ∑_{i∈D} ∏_{j∈I(i)∪\{i\}}|S_j|.\]

From the definition of the information set, for all $i∈D$ we have $I(i)∪\{i\}⊆C∪D,$ with size $1≤|I(i)∪\{i\}|=|I(i)|+1≤m≤n$ where $m$ denotes the upper bound of influence other nodes have on any decision node. Also, we have the number of decision nodes $0≤|D|≤n.$ Thus, we have the bounds

\[0 ≤ ∑_{i∈D}|𝐒_{I(i)}| |S_i| ≤ |D| \left(\max_{i∈C∪D} |S_j|\right)^{m}.\]

In the worst case, $m=n$, a decision node is influenced by every other chance and decision node. However, in most practical cases, we have $m < n,$ where decision nodes are influenced only by a limited number of other chance and decision nodes, making models easier to solve.