Stefan Richter [ARCHIVE] on Nostr: 📅 Original date posted:2021-08-24 📝 Original message: Good Morning Zmn! If ...
📅 Original date posted:2021-08-24
📝 Original message:
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.
Cheers,
Stefan
ZmnSCPxj <ZmnSCPxj at protonmail.com> schrieb am Di., 24. Aug. 2021, 01:06:
> Good morning Stefan,
>
> > Hi Zmn! That is some amazing lateral thinking you have been applying
> there. I'm quite certain I haven't understood everything fully, but it has
> been highly entertaining to read. Will have to give it a closer read when I
> get some time.
> >
> > As a first impression, here are some preliminary observations: While I
> highly like the Haskell-style datatype, and the algorithm we use does
> mostly use Dijkstra pathfinding, I think what is really important in your
> definition is the computeCost definition. This is what we would call the
> cost function IIUC, and in order to be able to solve min-cost flow problems
> it generally has to be separable and convex. I believe your datatype merely
> hides the fact that it is neither.
>
> Well, it really depends on what min flow cost algorithms actually assume
> of the "numbers" being used.
>
> For instance, it is well known that the Dijkstra-A\*-Greedy family of
> algorithms do not handle "negative costs".
> What it really means is that the algorithms assume:
>
> a + b >= a
> a + b >= b
>
> This holds if `a` and `b` are naturals (0 or positive), but not if they
> are integers.
> 1 + -1 = 0, and 0 >= 1 is not true, thus the type for costs in those
> algorithms cannot be integer types, they have to be naturals.
> However if you restrict the type to naturals, `a + b >= a` holds, and
> thus Dijkstra and its family of algorithms work.
>
> Thus, if you are going to use Dijkstra-A\*-Greedy, you "only" need to have
> the following "operations":
>
> `+` :: Cost -> Cost -> Cost
> `<` :: Cost -> Cost -> Bool
> zero :: Cost
>
> With the following derived operations:
>
> a > b = b < a
> a >= b = not (a < b)
> a <= b = not (b < a)
> a == b = (a >= b) && (a <= b)
> a /= b = (a < b) || (a > b)
>
> And following the laws:
>
> forall (a :: Cost) => a + zero == a
> forall (a :: Cost) => zero + a == a
> forall (a :: Cost, b :: Cost) => a + b == b + a
> forall (a :: Cost, b :: Cost, c :: Cost) => (a + b) + c == a + (b + c)
> forall (a :: Cost, b :: Cost) => a + b >= a
> forall (a :: Cost, b :: Cost) => a + b >= b
>
> As a non-mathist I have no idea what "separable" and "convex" actually
> mean.
> Basic search for "convex" and "concave" tends to show up information in
> geometry, which I think is not related (though it is possible there is some
> extension of the geometric concept to pure number theory?).
> And definitions on "separable" are not understandable by me, either.
>
> What exactly are the operations involved, and what are the laws those
> operations must follow, for the data type to be "separable" and "convex"
> (vs."concave")?
>
> I guess my problem as well is that I cannot find easy-to-understand
> algorithms for min cost flow --- I can find discussions on the min cost
> flow "problem", and some allusions to solutions to that problem, but once I
> try looking into algorithms it gets quite a bit more complicated.
>
> Basically: do I need these operations?
>
> `*` :: Cost -> Cost -> Cost
> `/` :: Cost -> Cost -> Cost --- or Maybe Cost
>
> If not, then why cannot `type Cost = UnifiedCost`?
>
>
> For example, this page:
> https://www.topcoder.com/thrive/articles/Minimum%20Cost%20Flow%20Part%20Two:%20Algorithms
>
> Includes this pseudocode:
>
> Transform network G by adding source and sink
> Initial flow x is zero
> while ( Gx contains a path from s to t ) do
> Find any shortest path P from s to t
> Augment current flow x along P
> update Gx
>
> If "find any shortest path" is implemented using Dijkstra-A\*-Greedy, then
> that does not require `Cost` to be an actual numeric type, they just
> require a type that provides `+`, `<`, and `zero`, all of which follow the
> laws I pointed out, *and no more than those*.
> `UnifiedCost` follows those laws (tough note that my definition of `zero`
> has a bug, `successProbability` should be `1.0` not `0`).
>
> In short --- the output of the cost function is a `UnifiedCost` structure
> and ***not*** a number (in the traditional sense).
>
> Basically, I am deconstructing numbers here and trying to figure out what
> makes them tick, and seeing if I can use a different type to provide the
> "tick".
>
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210824/75aad701/attachment-0001.html>;
📝 Original message:
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.
Cheers,
Stefan
ZmnSCPxj <ZmnSCPxj at protonmail.com> schrieb am Di., 24. Aug. 2021, 01:06:
> Good morning Stefan,
>
> > Hi Zmn! That is some amazing lateral thinking you have been applying
> there. I'm quite certain I haven't understood everything fully, but it has
> been highly entertaining to read. Will have to give it a closer read when I
> get some time.
> >
> > As a first impression, here are some preliminary observations: While I
> highly like the Haskell-style datatype, and the algorithm we use does
> mostly use Dijkstra pathfinding, I think what is really important in your
> definition is the computeCost definition. This is what we would call the
> cost function IIUC, and in order to be able to solve min-cost flow problems
> it generally has to be separable and convex. I believe your datatype merely
> hides the fact that it is neither.
>
> Well, it really depends on what min flow cost algorithms actually assume
> of the "numbers" being used.
>
> For instance, it is well known that the Dijkstra-A\*-Greedy family of
> algorithms do not handle "negative costs".
> What it really means is that the algorithms assume:
>
> a + b >= a
> a + b >= b
>
> This holds if `a` and `b` are naturals (0 or positive), but not if they
> are integers.
> 1 + -1 = 0, and 0 >= 1 is not true, thus the type for costs in those
> algorithms cannot be integer types, they have to be naturals.
> However if you restrict the type to naturals, `a + b >= a` holds, and
> thus Dijkstra and its family of algorithms work.
>
> Thus, if you are going to use Dijkstra-A\*-Greedy, you "only" need to have
> the following "operations":
>
> `+` :: Cost -> Cost -> Cost
> `<` :: Cost -> Cost -> Bool
> zero :: Cost
>
> With the following derived operations:
>
> a > b = b < a
> a >= b = not (a < b)
> a <= b = not (b < a)
> a == b = (a >= b) && (a <= b)
> a /= b = (a < b) || (a > b)
>
> And following the laws:
>
> forall (a :: Cost) => a + zero == a
> forall (a :: Cost) => zero + a == a
> forall (a :: Cost, b :: Cost) => a + b == b + a
> forall (a :: Cost, b :: Cost, c :: Cost) => (a + b) + c == a + (b + c)
> forall (a :: Cost, b :: Cost) => a + b >= a
> forall (a :: Cost, b :: Cost) => a + b >= b
>
> As a non-mathist I have no idea what "separable" and "convex" actually
> mean.
> Basic search for "convex" and "concave" tends to show up information in
> geometry, which I think is not related (though it is possible there is some
> extension of the geometric concept to pure number theory?).
> And definitions on "separable" are not understandable by me, either.
>
> What exactly are the operations involved, and what are the laws those
> operations must follow, for the data type to be "separable" and "convex"
> (vs."concave")?
>
> I guess my problem as well is that I cannot find easy-to-understand
> algorithms for min cost flow --- I can find discussions on the min cost
> flow "problem", and some allusions to solutions to that problem, but once I
> try looking into algorithms it gets quite a bit more complicated.
>
> Basically: do I need these operations?
>
> `*` :: Cost -> Cost -> Cost
> `/` :: Cost -> Cost -> Cost --- or Maybe Cost
>
> If not, then why cannot `type Cost = UnifiedCost`?
>
>
> For example, this page:
> https://www.topcoder.com/thrive/articles/Minimum%20Cost%20Flow%20Part%20Two:%20Algorithms
>
> Includes this pseudocode:
>
> Transform network G by adding source and sink
> Initial flow x is zero
> while ( Gx contains a path from s to t ) do
> Find any shortest path P from s to t
> Augment current flow x along P
> update Gx
>
> If "find any shortest path" is implemented using Dijkstra-A\*-Greedy, then
> that does not require `Cost` to be an actual numeric type, they just
> require a type that provides `+`, `<`, and `zero`, all of which follow the
> laws I pointed out, *and no more than those*.
> `UnifiedCost` follows those laws (tough note that my definition of `zero`
> has a bug, `successProbability` should be `1.0` not `0`).
>
> In short --- the output of the cost function is a `UnifiedCost` structure
> and ***not*** a number (in the traditional sense).
>
> Basically, I am deconstructing numbers here and trying to figure out what
> makes them tick, and seeing if I can use a different type to provide the
> "tick".
>
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210824/75aad701/attachment-0001.html>;