Optimization challenge : combinatorics, graphs, shortest path?

Question

Each Problem has one or many Solution(s).

Each Solution has its Weight.

Each Solution leads to zero or many Consequent Problems, that must be solved if this solution is used.

There are no cycles possible.

Given the root problem, goal is to find optimal combination of {Problem:Solution} pairs that gives minimum (or maximum) Total Weight (sum of weights of all used solutions), so all consequent problems of all used solutions are resolved.

Is there any algorithm with the runtime less or equal to $O((P+S)^2)$ that calculates the goal? other words - without recursively enumerating all possible combinations (via cartesian product).

Answer 1

You said it: graphs. Directed. With labeled nodes. The labels and edges are somewhat tricky, as follows.

Each node ''contains'' either a set of problems (a P-node) or a set of solutions (an S-node).

From each P-node, an edge goes to an S-node. The S-node contains the solutions to the problems in the P-node. The weight of the edge is the sum of the weights of all the problem-solution pairs.

For each solution $s$ in an S-node, an edge goes from that S-node to a P-node whose problem set consists of all the problems consequent from $s$. The edge carries weight zero.

This graph turns out to be a tree. Now find shortest paths from the root (a P-node whose set of problems consists of just the one root problem).

Answer 2

Define $w(s)$ to be the weight of a solution $s$, $P(s)$ to be the set of subsequent problems for solution $s$, and $S(p)$ the set of possible solutions for a problem $p$.

What we will do now is define the overall weight of a problem/solution, i.e., the amount of work that needs to be done to carry out that problem/solution taking the subsequent problems/solutions into account.

We'll say $W(s) = w(s)$ if $s$ has no subsequent problems and $W(s) = w(s)+ \sum_{p \in P(s)}W(p)$ otherwise where $W(p) = \min\{W(s) \mid s \in S(p)\}$. We look at the sum of the weights of the problems since all the subsequent problems for each solution need to be solved. Likewise, we look at the minimum of the solutions for a given problem since we want the cheapest solution. By starting at the trivial solutions (where $W(s) = w(s)$), you can eventually work your way up to the desired problem.