I need to solve a large-scale generalized network flow problem.

For reference, it is a pure network-flow model with the exception that arcs have a positive coefficient applied to flow on them. In my case I have supply nodes from which I send flow to sink nodes that absorb them. The flow, however, incurs a loss depending on the distance between the two nodes.

Google OR-Tools has an excellent network-flow solver, but only for pure flow models. Is there a publicly available and reasonably mature solver for generalized network models? If not, could anyone recommend an easy-to-implement solution algorithm that I can implement myself quickly?

  • 1
    $\begingroup$ Have you tried solving it as an LP? $\endgroup$
    – RobPratt
    Commented Nov 13, 2021 at 21:01
  • $\begingroup$ I did not yet, but it is the first thing I will try next week. I prefer originating flows to be integer, but probably can live with fractional values. I am kind of spoiled with the speed of Google's network flow solver, so hoping to find something like that for the generalized version. Also, I may have to solve this problem many times so computational requirement may be an issue. $\endgroup$ Commented Nov 13, 2021 at 21:05
  • 4
    $\begingroup$ Unlike pure network flow, generalized network flow will not typically yield integer optimal solutions. $\endgroup$
    – RobPratt
    Commented Nov 13, 2021 at 21:10
  • $\begingroup$ Good point, did not think of that. Given that commercial LP solvers are very fast these days, it should do it for me. Still I am curious about the availability of generalized network flow solvers. For very large problems it could make a significant difference compared to an LP solver. $\endgroup$ Commented Nov 13, 2021 at 21:14
  • $\begingroup$ What is the theoretical or computational evidence that there is a specialized algorithm for generalized network flows that will beat a general LP optimizer? Is there any collection of benchmark instances of generalized network problems? $\endgroup$ Commented Nov 15, 2021 at 7:45


Your Answer

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

Browse other questions tagged or ask your own question.