The min-cost flow does not use the expensive edge with cost 3.
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.
|Edge with capacity 10 and cost 1|
|Edge with flow 7, cap 10 and cost 1|
|Edge in residual graph, cost 1|
|Edge on negative cycle, cost 1|
Click on a node to select it as the source/starting node s
Click on a node to select it as the target/sink node t
Now the algorithm can begin. Click on next to start it
Computes the maximal possible flow while ignoring the cost information
The main loop repeatedly identifies negative cycles in the residual graph.
By running the Bellman-Ford algorithm we check for a negative cost cycle in the residual graph.
The negative cycle is removed from the residual graph by saturating one of the edges.
The algorithm terminated!
s ← pick(v)
t ← pick(v)
(* Initialize to max flow *)
CALCULATE MAX FLOW
(* Main Loop *)
WHILE negative cycle might exist DO
IF negative cycle exists
adjustment ← min(cost[e] |
e ∈ cycle-edges)
FOR e ∈ cycle-edges
flow[e] += adjustment
Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.
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.
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.
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
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.
Other graph algorithms are explained on the Website of Chair M9 of the TU München.
Studying mathematics at the TU München answers all questions about graph theory (if an answer is known).
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: