"Combinational" Decision Graph - Cheapest search algorithm

Question

I have a special kind of decision graph, where Multiple decisions must be made in combination, to accomplish the path. Not sure if Multiobjective or Combinational is the right term here, let me know if there is a better one. Picture better then words:

We have:

• Joining Nodes (e.g. "Start") which joins decisions or costs nodes together - meaning solution path MUST cover all edges of joining nodes.
• Decision Nodes (e.g. D1,D2,...) and Decision Edges (aka "local solution" - e.g. D1-1, D1-2,...) each solution path may cover only one of the edge of a decision.
• Costs Nodes - (e.g. 3,7,5...) that have cost/reward applied to the Paths that cover it. Technically any node even decision or joining can have costs associated. COSTS MAY BE NEGATIVE.
• Solution Path - goes from a starting node and must cover all edges of connected joining nodes and only one edge of each decision node it meets

Green is the cheapest Path for this example (D1-2,D2-1,D3-1) that you can calculate yourself empirically or combining all possible combinations and sorting by total costs. Total costs of Green path is $5.

Constraints:

• Costs may be negative - in this case it's a reward.
• Cycles are possible - they must be resolved as invalid path.
• Decisions are NOT binary

Goal:

Find the best (BigO runTime) algorithm to find cheapest path covering this kind of graphs (without iterating all possible combinations and calculating its costs)? Pseudo code would help. Also what is the name of such type of decision graph?

Answer 1

Your problem is $\mathcal{NP}$-hard, by reduction from $\mathcal{3SAT}$. Let $\Phi = \phi_1 \wedge \dots \wedge \phi_m$ be a CNF formula with variables $V = \{x_1, \dots x_n\}$. Let $\mathcal{L}(V)$ be the set of literals of $V$. Let joining nodes, decision nodes, cost nodes be defined as in your question.

For each $x_i$, we create four cost nodes $t_i$, $f_i$, both with cost $1$, representing an assignment of, respectively, true and false to $x_i$. Let $S$ be the set of all such nodes.

Let $\phi_i = \psi_{1i} \vee \psi_{2i} \vee \psi_{3i}$ be a clause with $\psi_{1i}, \psi_{2i}, \psi_{3i} \in \mathcal{L}(V)$. Without loss of generality, we may assume that $\psi_{1i}, \psi_{2i}, \psi_{3i}$ are literals obtained from different variables. Of the eight possible assignments of truth values to those variables, seven satisfy $\phi_i$. For each of those assignments, we create a joining node $c_{ki}$, which has as a successor every node $s \in S$ corresponding to the values relative to such assignment. For example, if the $k$-th assignment were "$x_\alpha$ true, $x_\beta$ false, $x_\gamma$ true", $c_{ki}$ would have $t_\alpha, f_\beta, t_\gamma$ as successors. Finally, we create a decision node $d_i$ with successors $c_{1i}, \dots, c_{7i}$ and let the starting node have as successors each of the $d_i$.

Now, observe that any solution path in the decision graph that we have built has weight at least $n$. In fact, whenever we encounter a fresh variable $x_i$, we are forced to take either $t_i$ or $f_i$, both of which have cost $1$. Furthermore, any path with cost not exactly $n$ has taken, by the pigeonhole principle, both $t_k$ and $f_k$ for some $k$, which means that it does not correspond to a consistent assignment of truth values to the variables of $V$.

On the other hand, an assignment of truth values to variables that satisfies $\Phi$ corresponds to a path of weight exactly $n$ (choose $t_i$ for every variable $x_i$ set to true, $f_i$ for every variable $x_i$ set to false, follow every arrow in the opposite direction).

We conclude that determining the optimal path is at least as hard as $\mathcal{3SAT}$, and consequently, as every problem in $\mathcal{NP}$.

As always with $\mathcal{NP}$-hard problems, your choice is to go with either heuristics or approximation schemes. If I may make a suggestion, problems like this are a good fit for logical programming tools, such as CSP/ASP.