0

We need to solve several problems, with these properties:

  • Each problem is in a category $A$, $B$, $C$, .... We label the problems $A_1$, $A_2$, ..., $B_1$, $B_2$, etc.
  • For each problem $X$, we have an estimate $d_X$ of its difficulty, i.e. of the resources needed to solve it.
  • The problems from different categories are related by a weight. This weight is interpreted as some kind of similarity or dependency. If we solve a problem, then the problems similar to (or dependent on) it will become easier to solve. For example, the weight $w_{A_1, B_2}$ tells us how the problems $A_1$ and $B_2$ are related. If we solve $A_1$, then our estimate $d_{B_2}$ of the difficulty of problem $B_2$ will be lowered by $w_{A_1, B_2}$.

The goal is to find the optimal path to solve all the problems, i.e. the path with the lowest total cost.

We could choose a greedy approach, i.e. iteratively solve the problem which is currently the easiest one. But there might be a more optimal path. There might be problems which are not easy to solve, but which are strongly related to many very difficult problems, which then become very easy to solve.

What kind of optimization problem am I looking at? What is the general way to solve such an optimization problem?

Bass
  • 511
  • I just saw that the categories do not really make sense, i.e. they do not influence the solution. So you might as well ignore the stuff about the categories. – Bass Feb 24 '20 at 17:33
  • 1
    Also I think that since we need to solve all problems anyway, the parameter $d_X$ does not matter, right? – sebastian Feb 24 '20 at 17:36
  • Can $w_{A, B}$ be different from $w_{B, A}$? – sebastian Feb 24 '20 at 17:39
  • @araomis If we assume that $w_{A,B}$ has an additive influence on $d_A$, then the parameters $d_A$ do indeed not matter. But we might generalize the problem by letting $w_{A,B}$ be a function that acts on $d_X$. – Bass Feb 24 '20 at 19:40
  • @araomis yes, the matrix does not need to be symmetric. If we think of $A_i$ as mathematical problems, then it is very asymmetric, since there are more and less general mathematical problems. – Bass Feb 24 '20 at 19:42
  • 1
    It might be connected to the problem Google solved with their PageRank algorithm. We have a directed, weighted graph of $n$ nodes, and we need some sort of propagation of "importance". – Bass Feb 24 '20 at 19:47

0 Answers0