Cycle Cancelling Algorithm

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.

## Legende

 Node Edge with capacity 10 and cost 1

## Which graph do you want to execute the algorithm on?

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

A occured when reading from file: the contents:

## Legende

 Node Source node Target node Edge with flow 7, cap 10 and cost 1 Edge in residual graph, cost 1 Edge on negative cycle, cost 1

## Algorithm status

### First choose a source node

Please click on a node in the network to select it as the source/starting node $s$. The flow is going to start from this node. It will have no incoming flow and the outgoing flow is equal to the flowsize.

### Then choose a target node

Please click on a node in the network to select it as the target/sink node $t$. The flow ends in this node. The incoming flow of this node is equal to the flowsize and it has no outgoing flow.

### Cycle cancelling flow algorithm

Now the algorithm can begin. Please click on next to start it.

### Initializing the flow

The algorithm computes the maximal flow, while ignoring the cost information, using the Edmonds-Karp algorithm, which is an implementation of the Ford-Fulkerson method.

The algorithm works as follows:

As long as there is a path in the residual network from the source $s$ to the sink $t$ with available capacity on all edges in the path, the algorithm sends flow along the shortest path until the edge with the smallest capacity saturates. The shortest path is found by using a breath first search. The algorithm repeats those steps until there is no augmenting path (path with available capacity) from $s$ to $t$ left.

More detailed description of the Ford-Fulkerson method and initialization of a maximal flow can be found here.

### Entering the main loop

When the algorithm has found the maximal flow $f\left(s,t\right)$ , it builds the residual network ${G}_{f}$ corresponding to this flow as follows:

Each edge $\left(v,w\right)\in G$ is replaced by two new edges $\left(v,w\right)$ and $\left(w,v\right)$.

The edge $\left(v,w\right)$ has cost $c\left(v,w\right)$ and residual capacity $r\left(v,w\right)=u\left(v,w\right)-f\left(v,w\right)>0$ , where $u\left(v,w\right)$ is the capacity of the edge and $f\left(v,w\right)$ is the flow through this edge.

The second edge $\left(w,v\right)$ has cost $c\left(w,v\right)=-c\left(v,w\right)$ and residual capacity $r\left(w,v\right)=f\left(v,w\right)>0$.

The main loop repeatedly identifies negative cycles (i.e. cycles whose total weight is negative) in the residual graph.

If no negative cycle is found the algorithm terminates.

### Find a negative cycle

One finds negative cycles in the residual network by running the Bellman-Ford algorithm as follows:

If $N$ is the number of nodes in the network, the algorithm is first executed $N-1$ times and should have found the shortest path from $s$ to $t$ . Then the algorithm is executed one more time and if the shortest path found in the $\left(N-1\right)$th execution has not changed, then there are no negative cost-directed cycles. Otherwise the algorithm takes a node the distance of which has changed, and goes from it via its ancestores until a cycle $W$ is found. $W$ is the negative cycle we were looking for.

### Cancel Cycle

When the algorithm finds a negative cycle, it augments

$\delta :=min\left\{r\left(v,w\right):\left(v,w\right)\in W\right\}$

units of flow in the cycle $W$ to saturate the edge with the minimal residual capacity, so the negative cycle $W$ is removed from the residual network.

Then the algorithm goes back to the main loop to examine the residual graph for other negative cycles.

### Finished

The algorithm terminated with maximal flow of:

-

and minimal cost for the flow:

-

The residual network contains no negative cost-directed cycles, therefore a minimum cost flow has been found.

### Test your knowledge on an exercise?

s ← pick(v)

t ← pick(v)

BEGIN

|

| (* Initialize max flow *)

| CALCULATE MAX FLOW $f\left(s,t\right)$ IN THE NETWORK

| USING THE FORD-FULKERSON ALGORITHM

|

| (* Main Loop *)

| WHILE (the residual network ${G}_{f}$

| | contans a negative cycle) DO

| |

| | EXECUTE BELLMAN-FORD ALGORITHM TO

| | IDENTIFY A NEGATIVE CYCLE $W$;

| | IF (negative cycle exists)THEN

| | | IDENTIFY cycle-edges $\left(v,w\right)\in W$

| | | $\delta :=min\left\{r\left(v,w\right):\left(v,w\right)\in W\right\}$

| | ENDIF

| | FOR ($\left(v,w\right)\in W$)

| | | $f\left(v,w\right)=f\left(v,w\right)+\delta$

| | ENDFOR

| |

| ENDWHILE

|

END

- -

## If the tab is changed the algorithm is terminated.

You can open another browser window to read another tab in parallel.

## Legende

 Node Source node Target node Edge in residual graph, cost 1 Edge on negative cycle, cost 1

## Answer the questions while running the algorithm!

### First choose a source node

Please click on a node in the network to select it as the source/starting node $s$. The flow is going to start from this node. It will have no incoming flow and the outgoing flow is equal to the flowsize.

### Then choose a target node

Please click on a node in the network to select it as the target/sink node $t$. The flow ends in this node. The incoming flow of this node is equal to the flowsize and it has no outgoing flow.

### Cycle cancelling flow algorithm

Now the algorithm can begin. Please click on next to start it.

### Initializing the flow

The algorithm computes the maximal flow, while ignoring the cost information, using the Edmonds-Karp algorithm, which is an implementation of the Ford-Fulkerson method.

### Entering the main loop

When the algorithm has found the maximal flow $f\left(s,t\right)$ , it builds the residual network ${G}_{f}$ corresponding to this flow.

The main loop repeatedly identifies negative cycles (i.e. cycles whose total weight is negative) in the residual graph.

If no negative cycle is found the algorithm terminates.

### Find a negative cycle

The algorithm runs the Bellman-Ford algorithm to find negative cycles in the residual network ${G}_{f}$.

### Cancel Cycle

When the algorithm finds a negative cycle, it augments

$\delta :=min\left\{r\left(v,w\right):\left(v,w\right)\in W\right\}$

units of flow in the cycle $W$ to saturate the edge with the minimal residual capacity, so the negative cycle $W$ is removed from the residual network.

Then the algorithm goes back to the main loop to examine the residual graph for other negative cycles.

### Finished

The algorithm terminated. The residual network contains no negative cost-directed cycles, therefore a minimum cost flow has been found.

s ← pick(v)

t ← pick(v)

BEGIN

|

| (* Initialize max flow *)

| CALCULATE MAX FLOW $f\left(s,t\right)$ IN THE NETWORK

| USING THE FORD-FULKERSON ALGORITHM

|

| (* Main Loop *)

| WHILE (the residual network ${G}_{f}$

| | contans a negative cycle) DO

| |

| | EXECUTE BELLMAN-FORD ALGORITHM TO

| | IDENTIFY A NEGATIVE CYCLE $W$;

| | IF (negative cycle exists)THEN

| | | IDENTIFY cycle-edges $\left(v,w\right)\in W$

| | | $\delta :=min\left\{r\left(v,w\right):\left(v,w\right)\in W\right\}$

| | ENDIF

| | FOR ($\left(v,w\right)\in W$)

| | | $f\left(v,w\right)=f\left(v,w\right)+\delta$

| | ENDFOR

| |

| ENDWHILE

|

END

## In this part you can test your knowledge: What would the algorithm do?

The algorithm will be executed normally, but will stop in a few places. Then you will have to predict, what the algorithm would do next.

Hint: Recall the description of the algorithm.

## If you switch tabs, the execution will be terminated.

You can open another browser window to read the description in parallel.

## Legende

 Knoten S/T Knoten Kante mit Kapazität 10 und Fluss 7. Kante im Residualgraphen. Kante auf augmentierendem Pfad.

## Build the corresponding residual netwprk!

In the following exercise you will get different networks $$N$$ with the respective capacities, flow values and costs $$u(e)$$, $$f(e)$$ and $$c(e)$$ for all edges $$e \in E$$, based on a current flow $$f$$.

Your task is to fill the missing residual capacities $$r(e')$$ bzw. $$r(e'')$$ of the out- and ingoing edges $$e'$$ und $$e''$$ in the corresponding residual network ${N}_{f}$.

## In this part you can practice the construction of residual networks!

You will get a network with current flow. Your task is to fill out the missing residual capacities and costs in the residual network!

Tip: Before you start read the information on residual networks again.

WARNING!

You can set the missing residual capacities and costs only once. When a value is set it can not be changed any more.

Good Luck!

## If you switch tabs, the execution will be terminated.

You can open another browser window to read another tab in parallel.