Good morning Stefan, > Good Morning Zmn! > > If you'd like to understand the min-cost flow problem and algorithms better, > I would really recommend the textbook we have been citing throughout the > paper. > > The algorithm you have found has a few shortcomings. It'll only work for the > linear min-cost flow problem, and it is very slow. In reality, we need to > deal with convex cost functions, and the algorithm we have used so far uses > an approach called capacity scaling in order to be much faster. It is indeed > complex enough that it has taken us about two months to understand and > implement it, discovering a nice heuristic in the process of making mistakes. > > Separable in this context means that you can simply add up the costs of the > edges to get the total costs. On second thought, your definition would > probably work here , by redefining adding up. > > Convex here means that for any two amounts x, y, the cost function f in the > interval x, y does not lie below the line connecting the two points (x, f(x)) > and (y, f(y)). The intuition here is that a linear approximation never > overestimates the real cost. I guess one would need a more involved > definition for your more complex coordinates.
Hmm, that does require that we define "subtract" and "multiply" operations, with certain additional rules. This is probably doable, especially since I think we do not need to multiply a `UnifiedCost` by another `UnifiedCost`, only a `UnifiedCost` by a `Rational`. ***HOWEVER*** I realized later that the `#zerobasefee` issue might not actually be a problem for the ***mincostflow*** algorithm, but rather a problem for the ***disect*** algorithm that converts a flow solution to an actual set of sub-payments. In that case, this effort is actually a dead end; it seems to me that, for the mincostflow algo at least, you can trivially add base fees, the issue is that once the disect algorithm gets its hands on the solution, base fees are problematic. In addition, if you tell me that it took you two months to do the algo, then that is an even greater concern --- this is possible to do with a small number of operations, but if we need to add more, like "subtract" and "multiply" operations, then the risk involved in the software engineering also increases, and the expected implementation time might take much, much longer due to complexity. For example, in CLBOSS I have a Dijkstra implementation that has inversion-of-control *and* allows users to parametrize "addition" and "comparison" operations, it is just a few dozen lines of code. However, the complexity of the code implementation would greatly increase if there is also a need to fill in "multiply" and "subtract" operations as well --- consider testing and other code quality needs. *And* if my conjecture is right --- that the `#zerobasefee` requirement is really a requirement of the ***disect*** algorithm rather than the ***mincostflow*** algorithm then the effort here would be pointless, we should focus more on the disect algo, which is why the new thread yet again. Regards, ZmnSCPxj _______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
