Weramajstor's blog

Min Cost Max flow state of art implementation
By Weramajstor, history, 2 years ago, In English

I am searching for state-of-art implementation of min cost max flow problem or reference to it. I am unable to come to sensible conclusion in reasonable time looking at what is currently avalible online, especialy in terms of min cost max flow that doesnt relly on maximum cost in edges. Thanks to anyone who sees this.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, # |
  Vote: I like it -84 Vote: I do not like it

Can't you just write it yourself? If not, why the fuck do you need it?

→ Reply
»
2 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Have you tried using bitset?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

While it is definitely not sate-of-the-art, just as a related observation on MCMF, I think a relatively easy to implement optimization that can be done to the most "canonical" algorithm is to use SPFA instead of Bellman-Ford when searching for an augmenting path of minimum cost (per unit of flow).

The cases where SPFA is as slow as Bellman-Ford occur when a path of minimum cost is made out of a lot of edges, which is something that does not happen in many flow networks, specially with the first augmenting paths found.

An example of a problem where this was useful to me is this problem. The time limit is 3 seconds, using Bellman-Ford I received a "Time limit exceeded verdict" (maybe because I was using python, but that is not the point I am trying to make, link to TLE submission), but after changing the calculation of the augmenting paths to SPFA, it got an "Accepted" verdict, and it took 300ms in the worst test case (link to AC submission).

→ Reply
»
2 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Here's are the two main algorithms ($$$V$$$ vertices, $$$E$$$ edges, $$$U$$$ max capacity, $$$F$$$ total flow, $$$C$$$ max edge cost):

  • Cost Scaling Push Relabel: $$$O(V^2 E \log(V\, C))$$$ or $$$O(V^3 \log(V\,C))$$$ worst-case (also has an $$$O(V^3 E)$$$ or $$$O(V^4)$$$ bound, which doesn't matter in practice, but you might care), $$$O(V E)$$$ in practice. Implementation by Min-25.
  • Network Simplex: Exponential worst case running time, but fast in practice, like $$$O(V E)$$$. See this blog for an explanation. Some of the fasted LibraryChecker submissions are based on the code from that blog.

In general, Network Simplex is better on dense graphs, while Cost Scaling Push Relabel is better on sparse graphs. I think this is due to Network Simplex pivots taking $$$O(V)$$$ time, while PR needs the full $$$O(E)$$$ time to relabel all vertices once.

Some less competitive algorithms:

  • Successive Shortest Paths: $$$O(F \cdot E \log V)$$$. Doesn't work with negative cost cycles! Needs an additional $$$O(V E)$$$ time to deal with negative cost edges in general! Is really only good for problems where the total flow is tiny (but there it beats everything else).
  • Capacity Scaling + Successive Shortest Paths: $$$O(E^2 \log V \log U)$$$: See this discussion. IIRC it's just worse than Push Relabel or Network Simplex.
  • Cycle canceling: $$$O(V E^2 C)$$$: Very slow, implemented in boost.
  • Min Mean Cycle canceling: $$$O(V^2 E^3 \log V)$$$. Very slow, only of theoretical interest due the running time only depending on $$$V$$$ and $$$E$$$.
→ Reply