2
$\begingroup$

I'm a bit confused about the definition of the Minimum Cost Flow problem, in terms of the edge cost (or weight) values.

I don't remember a integral requirement on the cost/weight values for the edges when first learning the problem. But when I start to look for implementations, most algorithmic code I found require the edge weights to be integers. (I haven't delved into Simplex or LP related code though). For example, in here, and here, weight values are defined as int cost; and typedef long long int price_t; ... price_t _cost; // cost of arc;, resp.

Boost Graph Library (BGL) seems to allow different weight types through C++ templates, but the examples in documentation are using integer weight values. The only use of floating weight values I can find is a SO question about the errors associated with using the floating points (https://stackoverflow.com/questions/35746487/). Google optimization tool also has a bug/feature request for floating point weight values, which is closed immediately stating it only supports int64, currently.

Is there a fundamental reason behind this lack of real valued weights in mincost flow implementations (such as complexity)? That is, is the real valued Min Cost Flow more difficult or impossible to solve, or is this just a coincidence?

$\endgroup$
3
$\begingroup$

In the case of the Ford-Fulkerson algorithm, yes, it's due to complexity. When the edge weights/capacities aren't integers, things get really annoying, really fast.

If you allow all real numbers, you can end up with an instance that doesn't terminate. Normally, you augment paths until you can no longer do so. An irrational capacity value could allow the algorithm to continually find smaller and smaller augmenting paths.

Uri Zwick came up with a good example to show this:

Non-terminating graph

Consider the flow network shown on the right, with source $s$, sink $t$, capacities of edges $e_1$, $e_2$ and $e_3$ respectively $1$, $r=(\sqrt{5}-1)/2$ and $1$ and the capacity of all other edges some integer $M \ge 2$. The constant $r$ was chosen so, that $r^2 = 1 - r$. We use augmenting paths according to the following table, where $p_1 = > \{ s, v_4, v_3, v_2, v_1, t \}$, $p_2 = \{ s, v_2, v_3, v_4, t \}$ and $p_3 = \{ s, v_1, v_2, v_3, t \}$.

Non-terminating example steps

Note that after step 1 as well as after step 5, the residual capacities of edges $e_1$, $e_2$ and $e_3$ are in the form $r^n$, $r^{n+1}$ and $0$, respectively, for some $n \in \mathbb{N}$. This means that we can use augmenting paths $p_1$, $p_2$, $p_1$ and $p_3$ infinitely many times and residual capacities of these edges will always be in the same form. Total flow in the network after step 5 is $1 + 2(r^1 + r^2)$. If we continue to use augmenting paths as above, the total flow converges to $\textstyle 1 + 2\sum_{i=1}^\infty r^i = 3 > + 2r$, while the maximum flow is $2M + 1$. In this case, the algorithm never terminates and the flow doesn't even converge to the maximum flow.

(Wikipedia)

The Stoer-Wagner algorithm will work with non-integer capacities, and so will Simplex/LP algorithms.

$\endgroup$
2
  • $\begingroup$ Thanks a lot for your input. I understand that there is some implications of using integer vs floating point edge capacity. But I was asking about the edge cost of network flow algorithms. Any pointers there? $\endgroup$ – tinlyx Jun 10 '18 at 5:15
  • $\begingroup$ I'm so sorry, I must've misread Min Cost Max Flow as Min Cut / Max Flow. For Min Cost (with edge costs), I don't have much to offer outside of LP solutions. $\endgroup$ – user116037 Jun 11 '18 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.