node_recommender: Low-fee routing maxflow is calculated incorrectly

[ajpwahqgbi]

Consider the following graph described by the edges (src, dest, cost): (a, b, 0.1), (a, c, 0.8), (b, c, 0.0), (b, d, 0.8), (c, d, 0.8). Each node and each edge would be contained in the low-fee reachable subgraph with a cost threshold of 1.0. The naive maxflow--i.e. the way that the maxflow is currently calculated--between node a and node d is 2: ((a, b), (b, d)), ((a, c), (c, d)).

However, despite the fact that all nodes and edges are low-fee reachable, not all routes within the low-fee reachable subgraph satisfy the cost constraint. Specifically the flow ((a, c), (c, d)) has a cost of 1.6 and violates the cost constraint.

The problem is further complicated by the fact that fees in the LN are vectors and not scalars.

Luckily it appears that T.H Szymanski from McMaster university has a good solution to the problem in the IEEE WCNC 2012 paper "Achieving Minimum-Routing-Cost Maximum-Flows in Infrastructure Wireless Mesh Networks".

[ajpwahqgbi]

Meh, that paper has a complicated double-LP encoding that looks like a PITA. Maybe just implement a MaxSMT encoding and solve with help from pysat, specifically their RC2 implementation

Also see https://sat-smt.codes/main.html, and especially https://sat-smt.codes/SAT_SMT_by_example.pdf#1a8 (but obviously our graph is not planar) and its implementation https://sat-smt.codes/current_tree/puzzles/numberlink/MaxSAT/numberlink_WBO.py

Another idea is to see what LEMON provides and if needed write a Python wrapper around it.

Google's OR-Tools might work, too. A simple greedy approach, iteratively finding and removing the min-cost flow for as long as the min-cost flow's cost is below the threshold, might work, too, but:

1. I am skeptical that it's guaranteed to give optimal results although I haven't tried to prove it one way or another. However it can still give a lower bound for the achievable flow below the cost threshold, which is nearly as useful as optimal results.
2. At least if done naively, it may be excruciatingly slow and duplicate lots of effort.

[ajpwahqgbi]

The greedy min-cost flow removal approach is definitely not guaranteed to give optimal results. Consider the following graph, described by its edges (node1, node2, cost): (s, a, 0.1), (s, b, 0.4), (a, c, 0.1), (a, d, 0.5), (b, c, 0.4), (d, t, 0.2), (c, t, 0.1). This approach first removes the lowest-cost s-t flow ((s, a), (a, c), (c, t)) for a cost of 0.3, then finds there are no remaining paths to t and returns 1. But the optimal answer is 2: ((s, a), (a, d), (d, t)) for a cost of 0.8 and ((s, b), (b, c), (c, t)) for a cost of 0.9.

While a lower bound may be useful, this might be too loose of a lower bound.

FWIW, an anti-greedy approach where we iteratively find and remove the flow with the highest cost less than the threshold is also not optimal. Consider an isomorphic graph with different costs: (s, a, 0.5), (s, b, 0.3), (a, c, 0.2), (a, d, 0.1), (b, c, 0.3), (d, t, 0.1), (c, t, 0.2). Now the algorithm first removes the flow ((s, a), (a, c), (c, t)) for a cost of 0.9 and stops, while the optimal answer is the same two flows as before, now with costs 0.7 and 0.8.