Cost minimal maximum flow in graphs: Ford-Fulkerson 3
The Ford Fulkerson algorithm developed by Ford and Fulkerson is classified into the graph theory.
Inhaltsverzeichnis
Idea
Instead of simple minimizing the costs or distances between two nodes (start node - end node)you are faced with transporting resources coupled with specific transport ways (constrained and with different costs). The main question is here: “Which edges do we have to use in order to minimize the costs and maximizing the flow considering that we want to transport from a start node to an end node and the edges are constrained”.
The principle of the algorithm is based on the Dijkstra algorithm: you determine the cost efficient path between the start and end node and let as much as possible units flow over this path. After this step we reach the limit of at least one edge.
So we get a modified graph on which the Dijkstra algorithm has to be executed again. Now there is a second path where we can transfer further units. The capacity of each edge in this cycle is limited by the initial capacity reduced by the units already passed through.
We proceed until we can’t transfer any more flow from the start to the end node.
Mathematical Formulation (LP model)
Objective function:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): min\ C \ \sum_{ij}c_{ij}*f_{ij}
and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max\ F \ \sum_{ij}f_{se}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \forall i;j > 0;
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): s \in \{1..i..\}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): e \in \{1..j..\}
s = start node; e = end node
restrictions:
1) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f_{ij} \ge 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \forall i;j > 0
2) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \forall i;j > 0
3) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f_{ij} \le k_{ij}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \forall i;j > 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): k_{ij} \ge 0
Algorithm of Ford & Fulkerson
1. Determination of cost minimal path from start node to end node(with Dijkstra) which still has free capacity
End if no route left.
2. Add the highest possible flow (determined by the minimum of the maximal possible flow of every concerned edge) to the selected path
Return to step 1
Example
The following graph provides four nodes connected with their respective edges defined by costs and capacity.
The first column of the tables beside the edges means the costs per unit whereat the first row of the second column represents the maximal capacity of this edge. The rows below represent the accumulated flow of this edge.
The first column of the table beside the node means the predecessor node, the second column means the accumulated costs from the start node up to the respective node and the third means the maximal flow from start node up to the respective node.
Problem:"Which edges do we have to use in order to minimize the costs and maximizing the flow considering that we want to transport from a start node to an end node and that the edges are constrained"
First step…
First we find out the cheapest path with the Dijkstra-algorithm namely path A-C-B-D with costs of 6 per unit. The maximal flow that could be transferred - following A-C-B-D - is limited by 2 (edge B-D) with costs of 6 per unit
Second step…
Edge B-D can’t be used anymore because of reaching its capacity limit of 2. Now we have to find out the next cheapest path considering that path B-D has fallen away. With Dijkstra we get path A-C-D with accumulated costs of 9 per unit and a flow of 2 units. The maximal flow of this path is just 2 due to edge A-C where we transferred already 2 units in the previous step. So this capacity limit constraints this flow.
Third step…
Edge A-C reached the capacity limit of 4 units so it remains just one path we can choose namely A-B-C-D. At edge A-B is a capacity limit of 3 units. That’s why we can transport just 3 (max flow) units from A to D over B and C. In step one 2 units were transferred from C to B (path A-C-B-D) but now we are transferring 3 units from B to C. Because of the fact that (in this case) it is allowed to exchange bidirectional we can allocate the transfers. In fact we want to deliver 2 units of our product from C to B but 3 from B to C. Hence it’s cheaper to keep 2 of the products instead of strictly delivering them to the respective node. We are also able to safe costs. In consequence we just transfer one unit from B to C. Consider that nevertheless we have to deliver 3 units from C to D (as originally sent from A)
Summary of minimal costs maximal flow
In conclusion the best efficient possibility to transfer units of our product from A to D will be at first using path A-C-B-D (2 units with costs of 6 per unit) then A-C-D (2 units with costs of 9 per unit) and last A-B-C-D (3 units with costs of 12 per unit) so that we finally reach a maximal flow of 7 units with minimal costs of 66
| path | quantity q | costs c [per unit] | quantity*costs |
|---|---|---|---|
| A-C-B-D | 2 | 6 | 12 |
| A-C-D | 2 | 9 | 18 |
| A-B-C-D | 3 | 12 | 36 |
| ∑ | 7 | 66 |
Sources
Script 'Operations Research' SS13 chapter 3
