I'm trying to find an efficient, publically available algorithm, preferably with implementation, for solving maximum flow in a generalized (non-pure) network with gains. All multipliers, capacities and flow values are non-zero integers.
Does such an algorithm exist, or is this problem not solvable in polynomial time?
The first (strongly) polynomial-time algorithm was published by Végh in 2013, and has since been improved by Olver and Végh to a worst-case runtime in O((m + n log n) m n log(n^2 / m)). But I don't know of any public implementation for this algorithm.
The linked papers also contain references to earlier (weakly) polynomial-time algorithms as well as approximate algorithms, some of which may have public implementations. (This older paper by Tardos and Wayne mentions a C++ implementation.)