3
$\begingroup$

I am a Bitcoin / Lightning Network open source developer and researcher and new here but very active on the sister site. In the context of my research I discovered the field of operations research and I have a problem that I am sure has been solved before but I fail to find the solution or the problem in the literature.

Background

In my context I have a transportation network where the convex (in practice I linearize it but I thought I describe the problem in the original form) cost function for each arc with capacity $c$ encodes the uncertainty weather $a$ units can be forwarded. This is expressed as:

$$ cost(a) = -\log(P(X>=a)) = -\log\left(\frac{c+1-a}{c+1}\right) $$

Let $mcf(a)$ be the solution of the corresponding Minimum Cost Flow Problem as described in this research article. Then $P(mcf(a)) = 2^{-cost(mcf(a))}$ can be seen as the probability for $a$ units to successfully flow through the network.

for a fixed source and sink node pair on a small example network I have computed the probabilities for various amounts of goods for the resulting flows as can be seen in this diagram:

Distribution of success Probabilities for various units (called sats) to flow through the network

The probability of success drops stronger than exponentially with more units to be sent. Which makes sense from a probabilistic perspective.

Actual Question / Problem

One can multiply for each amount $a$ the amount with the resulting probability $p$ of the corresponding minimum cost flow and receive the expected amount that will be delivered through the network. For the small sample network I have done this in the following diagram for every possible amount $a$ that produced a feasible flow.

Expected amount that can flow through a network with probabilistic forwarding on arcs depending on the attempted sent out amount

So my goal is to find the maximum of this function without having to solve the min cost flow problem several times. So I seek the expectation value or the solution of

$$ EV = argmax_{a}\{a\cdot P(mcf(a))\} $$

Of course I can do this as done here in a small network by computing the result of the minimum cost flow problem for every amount but I wish to find a more straight forward approach for this second stage optimization problem.

While searching the literature I found stochastic programming but I feel a bit uncertain if I have to learn the techniques in that field to solve my problem. However the problem seems to me to be common enough in the sense that it should be known. Of course the most desirable goal would be if an open source software solver for the problem already existed.

$\endgroup$

2 Answers 2

1
$\begingroup$

Since you seem to have figured out a distribution for minimum cost flow (appears like Log-normal) you can try 2- stage stochastic programming using SAA techniques. LINDO Systems or model offers a very helpful tutorial on that.
You will need expected value as the objective (that's always part of objective formulation) but need to pick up a sample size for constraints.

$\endgroup$
0
$\begingroup$

This open-source software solver can handle stochastic programming problems, including the scenario approach. PySP is a python based modeling framework for stochastic programming that allows us to easily implement and solve stochastic optimization problems using a variety of solvers. Another popular solver for stochastic programming problems includes AMPL & GAMS. As stated above if you are having access to a suitable solver then using SAA methods we can efficiently solve this problem without having to solve the minimum cost flow problem multiple times.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.