1
$\begingroup$

I have a problem that can be represented as an optimization problem. Sometimes, solver engines report infeasible depending on the parameters I have at hand. The root cause is numeric ranges.

Description

Problem parameters consist of a set of nodes and edges. Each edge is bidirectional and there could be several edges between 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 the 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 $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_{j-i}$.

If we move number $X_a$ from node to node, then the rule says what number $X_{b}$ on the target node can be formed using the next formulas.

$(E_a+X_a) * (E_b{} - X_{b})=C_{a<->b}$, where $C$ is specific constant equal to $E_{a}*E_{b}$ in the edge.

So $X_b = E_b - C/(E_a+X_a)$ is number one gets from moving it from node to node.

Moving the number in the other direction is calculated the same way.

Movement of number reduces $E_b$ amount and increases $E_a$ amount in the edge.

After playing with formula, it would be seen:

  • edge multiplies or divides number
  • maximal number of $X$ cannot be bigger than the amounts in the edge.
  • Each increase of $X_a$ leads to an increase of $X_b$, but the amount of change of $X_b$ obtained is smaller and smaller with for next same amount of increase in $X_a$.

Edges amid nodes and their amounts form constraints.

$X$ can be split into parts and moved along several routes. For instance, moving $X_i$ from $N_i$ to $N_j$ and $N_k$, such that $k≠j$. Ratio of split can be any.

It is also possible to merge numbers. For instance, moving from $X_i$ and $X_j$ to $X_k$, such that $i \ne j \ne k$. After merge $X_k$ can be propagated as one number. Sometimes cannot merge, and 2 numbers will flow.

Example

Let's consider some cases where numerics go wild.

We have 5 nodes, $N_1 .. N_5$.

Each hop on multiplies by $10^2$.

If we have number $10^3$ on $N_1$ and target is to reach $N_5$ with maximum number, it will lead to $10^{13}$. If we start on $N_5$ with a small number, it will lead to a really small number on $N_1$.

Problem complexity and size

In our problem parameters, there are many nodes and many edges, there are more than one route from node to node. And numbers can get really low and then high on one route and be whatever on another route.

We can have hundreds of nodes and hundreds of edges.

Number may be split to move over several routes at the same time to reach the final node.

Starting numbers can be as small as $10^3$ and as big as $10^{18}$.

Edge amounts can be $10^6$ up to $10^{24}$.

Additionally, we have some constant factors which are cut from $X$ during move over edges, not obeying $C$ formula, deduced after arrival on the target node.

Also, nodes form clusters. Moving numbers from one cluster to another has some other constant factor removed from $X$ when it travels along the edge connecting two nodes from different clusters, sometimes we do not want to leave the cluster.

That leads solvers, SCIP and others, to detect Nonlinear problem and it solved in floating point arithmetics(not MILP).

Question

How to scale edge numbers and $X$ numbers the way that will likely lead to problem feasibility?

I have already did the following:

  • found all routes from the start node to any other node, and produced a total approximated multiplier of each travel. It is an approximation because it does not consider the size of move, just spot number of minimal amount assuming edge amounts are infinite.
  • in case of relatively big edge amounts, capped these to some smaller amount in comparison to $X$. Comparison is done using the above heuristic.
  • any edge with a really small amount against $X$ eliminated.

I tried to scale up or scale down all amounts, but that does not work as need some scale in to put all numbers in the possible middle range.

I am searching for some algorithm/rule that tells how to scale edges numbers ensuring that routes are feasible.

What is the application?

Application of finding the best way to swap funds on crypto exchanges and move funds along bridges, paying fees and gas costs.

User wants to give some assets and get another asset. Numerics can be wild because of the big difference in decimals used in assets and asset prices.

$\endgroup$
7
  • 1
    $\begingroup$ cs.stackexchange.com/q/165350/755 $\endgroup$
    – D.W.
    Commented Feb 3 at 5:53
  • $\begingroup$ yeah, CS based approach can be used to allow to scale in numeric range of OR problem. CS heuristic can be used to find numeric ranges to scale to make OR engine happy. $\endgroup$ Commented Feb 3 at 17:09
  • 1
    $\begingroup$ Is it possible to move a number to two diferrent nodes simultaneously? For instance, moving $X_i$ from $N_i$ to $N_j$ and $N_k$, such that $k \neq j$? $\endgroup$ Commented Feb 13 at 12:11
  • 1
    $\begingroup$ yes, thank you, split into any values is possible $\endgroup$ Commented Feb 13 at 17:29
  • 1
    $\begingroup$ Ok, thanks. So, is it possible to "merge" numbers? For instance, moving, both, $X_i$ (from $N_i$) and $X_j$ (from $N_j$) to $N_k$, such that $k \neq j \neq i,\ k \neq i$? $\endgroup$ Commented Feb 13 at 18:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.