# Optimization of value over network flow from start to end node with constant function multiplier edges tractability

Our problem is similar to this, but it details various approaches we can make.

The problem also was formulated operation research, but got hit with numeric limitations.

Here we seeking to find reference algorithms per each complexity added, its pratical limitations (limited numbers N, formulas for constant C factors to estimate if these fit modern hardware, probabalistic solutions)

Description

Problem parameters consist of set of nodes and edges. Each edge is bidirectional. There could be several edges amid any two nodes.

Each edge has two numbers associated with it. Before explaining what these two numbers mean, let me explain what is concrete input parameter into problem which varies and objective.

Problem input tells that we have some number $$X_i$$ on node $$N_i$$, and we want to reach node $$N_j$$ with maximal number possible on target $$X_j$$.

Each move from any node to any specific node multiplies or divides number.

But how? Recall edge has two numbers with it, $$E_{i->j}$$ and $$E_{i<-j}$$.

If we move number $$X_i$$ from node to node directly connected by edge, then rule telling what would be number $$X_i$$ on target node can be formed using next formulas.

$$(E_i+X_i) * (E_j{} - X_{j})=C_{i<->j}$$, where $$C$$ is specific constant equal to $$E_{i}*E_{j}$$ in the edge.

So $$X_j = E_j - C/(E_i+X_i)$$ is number one gets from moving it from node to node.

Moving number other direction is calculated same way.

Movement of number reduces $$E_j$$ amount and increases $$E_i$$ amount in the edge.

After playing with formula, it would be seen:

• edge multiplies or divides number
• maximal number on of $$X$$ cannot be bigger than amounts in the edge.
• Each increase of $$X_i$$ lead to increase of $$X_j$$, but change of amount of $$X_j$$ obtained is smaller and smaller with for next same amount of increase in $$X_i$$, diminishing returns.

Edge weights getting updated after a number moves across the edge, but weights product remains constant.

What is the problem?

Simple target of graph search can be postulated as

Start on N_a with number X_i, find maximal number X_j one may get on some target X_j. X can be moved as whole and never can be split What is maximal $$X_j$$ we can get on target node?

I have python code for this target and it works fast if I do not allow multiplying loops.

Adding loops

There is $$N_1 \rightarrow N_2 \rightarrow N_3$$ path which gives some $$X$$ in the end.

But if we on $$N_2$$ visit $$N_4$$, and go back to $$N_2$$, and then to $$N_3$$ we get more $$X$$ in the end. That is loop.

On top of single route, we can try to split $$X$$ amid several routes.

Solution examle can be:

\begin{align} 70\% \text{ via } N_1 \rightarrow N_2 \rightarrow N_3 \\ 30\% \text{ via } N_1 \rightarrow N_4 \rightarrow N_3 \end{align}

Any other splits are possible. Formula $$C$$ may be important here.

Barries

When some edge crossed, some constant amount of $$X_b$$ is deduced from $$X_i$$.

When some edge cross, some proportional amount of $$P_b$$ is deduced from $$X_i$$. $$P_b$$ is usually less than one part of hundred.

So $$X^{fin}_i = (X_i - X_b)*(1-P_b)$$

In case of proportional barrier, there is no $$C$$ function operating in edge. In this case each side of edge have $$L$$ number which is limit of what can cross edge.

Hyperedges

One edge can connect more then too nodes.

Formula $$C$$ expanded to $$E_i * E_j *E_k = C$$

Problem complexity and size and reasonable constant caps

We can have hundreds of nodes and hundreds of edges. Maximal number few thousands.

We really not so care splits under $$0.1\%$$ of amount.

Also maximal length of path can be considered $$10$$ nodes, but usually we fine with $$5$$.

We ok to try more complicated algorithm on shorter path and simpler on longer path, and find best.

Not all edges are subject to $$C$$, there could be others, but $$C$$ is good approximation.

Question

What are reference algorithms to solve problems and their combinations?

How to estimate hardware requirements for possible calculations?

Are there some approximate randomized and/or parallel algorithms possible, and their implementations?

• or.stackexchange.com/q/11603/2415
– D.W.
Feb 3 at 5:53
• @InuyashaYagami, yes. fixed. Feb 3 at 16:51
• @D.W. yeah, same problem can be looked and numerically solved different ways. what appeared to be true, until I run graph based presolver (CS based), OR engines cannot be scaled to be feasible. That CS based (graph or metaheurisics) is called oracle in my domain. Feb 3 at 16:52