Cycle Cancelling Algorithm Technische Universität München

Introduction
Create a graph
Run the algorithm
Description of the algorithm
More

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.

What do you want to do first?

Download Graph

Legende

	Node
	Edge with capacity 10 and cost 1

Legende

Which graph do you want to execute the algorithm on?

Start with an example graphs:

Select

Modify it to your desire:

To create a node, double-click in the drawing area.
To create an edge, first click on the output node and then click on the destination node.
The edge weight can be changed by double clicking on the edge.
Right-clicking deletes edges and nodes.

Download the modified graph:

Download

Upload an existing graph:

occured when reading from file:

the contents:

What next?

Download SVG

Legende

	Node
	S/T node
	Edge with flow 7, cap 10 and cost 1
	Edge in residual graph, cost 1
	Edge on negative cycle, cost 1

Legende

Algorithm status

rewind fast forward

Explanation
Pseudocode
Variable State

First choose a source node

Click on a node to select it as the source/starting node s

Then choose a target node

Click on a node to select it as the target/sink node t

Cycle cancelling flow algorithm

Now the algorithm can begin. Click on next to start it

Initializing the flow

Computes the maximal possible flow while ignoring the cost information

Entering the main loop

The main loop repeatedly identifies negative cycles in the residual graph.

Find a negative cycle

By running the Bellman-Ford algorithm we check for a negative cost cycle in the residual graph.

Cancel Cycle

The negative cycle is removed from the residual graph by saturating one of the edges.

Finished

The algorithm terminated!

s ← pick(v)

t ← pick(v)

BEGIN

(* Initialize to max flow *)

CALCULATE MAX FLOW

(* Main Loop *)

WHILE negative cycle might exist DO

EXECUTE BELLMAN-FORD

IF negative cycle exists

IDENTIFY cycle-edges

adjustment ← min(cost[e] |

e ∈ cycle-edges)

FOR e ∈ cycle-edges

flow[e] += adjustment

END

Variable State

cycle	adjustment
-	-

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.

Minimum-cost Flows

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.

Where can I find more information about graph algorithms?

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).

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
Link: https://www-m9.ma.tum.de/graph-algorithms/flow-cycle-cancelling

The Min-Cost Flow Problem

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

What do you want to do first?

Legende

Legende

Which graph do you want to execute the algorithm on?

Start with an example graphs:

Modify it to your desire:

Download the modified graph:

Upload an existing graph:

What next?

Legende

Legende

Algorithm status

First choose a source node

Then choose a target node

Cycle cancelling flow algorithm

Initializing the flow

Entering the main loop

Find a negative cycle

Cancel Cycle

Finished

Variable State

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Minimum-cost Flows

Idea of the Cycle Cancelling Algorithm

What now?

Create a graph and play through the algorithm

What is the pseudocode of the algorithm?

How efficient is the algorithm?

References

Literature

Web resources

Where can I find more information about graph algorithms?

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