The min-cost flow does not use the expensive edge with cost 3.

The Min-Cost Flow Problem

Road system, water pipes, or data networks are the motivation for a class of optimisation problems termed flow problems. The shared characteristic for this type of system is that some kind of resource has to be transported over the edges of a graph, which are constrained to only carry only up to a certain amount of flow. For some instances edges also have other properties, making it useful to assign a cost for using a specific edge - for example variable toll charges in a network of highways.

In this kind of setting it is interesting to compute how a certain flow can be routed through the network using the cheapest possible route. This problem is called the minimum-cost flow problem.

This applet presents the cycle cancelling algorithm to calculate a minimum-cost flow on a given network.

Minimum-cost flow is a classic optimisation problem, which can be motivated by a typical decision problem: Given a transport network of roads, whose usage is restricted by varying capacities and incurs different cost, find the cheapest way to transport the maximal amount of goods from location s to location t.

The corresponding mathematical model is made up of the following information: A directed graph G(V,E) modeling the network topology. An upper limit on the capacity of each edge, given by a function u(e) | e ∈ E, and the cost function c(e) which models how expensive is is to send one unit of flow along each edge. The last information required is a start and a goal node.

The solution to the problem is a flow f(e) determining the usage of each edge which minimizes the total cost. The cost incurred by each edge is simply it's flow times the cost of the edge. The solution also has to fulfill some constraints imposed on flows in general - each edge can only carry up to u(e) units of flow, and for all non-terminal nodes in the network the sum of incoming and outgoing flow has to be equal.

The total amount of flow has to be fixed before optimising for cost. In this application we look at the specific problem of finding the cheapest realisation of the largest possible flow through the network - the min cost max flow problem.

Idea of the Cycle Cancelling Algorithm

The cycle cancelling algorithm takes an iterative approach, starting with any valid flow with the desired magnitude (e.g. generated by a max-flow algorithm). It then iteratively reduces the cost by moving the flow to cheaper edges without violating constraints.

Possible ways to redirect the flow can be found by evaluating the residual graph of the flow: Sending flow along a cycle in the residual graph always leads to another valid flow and keeps the total flow constant. If the sum of the costs for the edges in the cycle is negative, changing the flow will reduce the overall cost and improve the solution.

Negative cycles can be found by running the Bellman-Ford algorithm. After identifying a cycle, some amount of flow can be sent along all it's edges, until the one with the lowest capacity saturates. This removes the edge from the residual graph, thereby removing the cycle. Since the new residual graph might still contain other cycles, the algorithm has to iterate and run the Bellman-Ford algorithm again.

What now?

Create a graph and play through the algorithm

What is the pseudocode of the algorithm?

Input: directed graph G=(V,E), capacity function u(e), cost function c(e), source and target node
Output: minimum-cost max flow f(e)

BEGIN
(* Initialize to max flow *)
f = CALCULATE MAX FLOW()
(* Main Loop *)
WHILE negative cycle might exist DO
CONSTRUCT RESIDUAL GRAPH G'(V,E') WITH CAPACITIES u'(e)
EXECUTE BELLMAN-FORD ON G' FROM TARGET NODE
IF negative cycle exists
IDENTIFY cycle-edges
adjustment ← min(u'(e) | e ∈ cycle-edges )
FOR e ∈ cycle-edges
f(e) += adjustment
END

How efficient is the algorithm?

The generic cycle cancelling algorithm has the non-polynomial runtime O(|E| |V| C), with C being the total cost of the initial flow - as each iteration requires a run of Bellman-Ford in O(|E| |V|) and reduces the cost by at least 1.

There are multiple more complex algorithms for the min-cost flow problem which achieve better runtimes. One adaption of the cycle cancelling algorithm is minimum mean cycle cancelling, which already results in a strongly polynomial algorithm. Other algorithms can e.g. be found here.

References

Literature

[GT89]

Andrew V. Goldberg and Robert E. Tarjan (1989). "Finding minimum-cost circulations by canceling negative cycles". Journal of the ACM. 36 (4): 873–886. doi:10.1145/76359.76368.

A last remark about this page's content, goal and citations

Chair M9 of Technische Universität München does research in the fields of discrete mathematics, applied geometry and the mathematical optimization of applied problems. The algorithms presented on the pages at hand are very basic examples for methods of discrete mathematics (the daily research conducted at the chair reaches far beyond that point). These pages shall provide pupils and students with the possibility to (better) understand and fully comprehend the algorithms, which are often of importance in daily life. Therefore, the presentation concentrates on the algorithms' ideas, and often explains them with just minimal or no mathematical notation at all.

Please be advised that the pages presented here have been created within the scope of student theses, supervised by Chair M9. The code and corresponding presentation could only be tested selectively, which is why we cannot guarantee the complete correctness of the pages and the implemented algorithms.

Naturally, we are looking forward to your feedback concerning the page as well as possible inaccuracies or errors. Please use the suggestions link also found in the footer.

To cite this page, please use the following information:

Title: Cycle-Cancelling Algorithm

Authors: Quirin Fischer, Wolfgang F. Riedl; Technische Universität München