Introduction
In network optimization theory, maximum flow problems mean finding a practical maximum flow within a capacity network from an origin to a destination. There are different ways to solve this problem. In one method, by writing the equivalent of the linear programming problem of this problem and solve with the simplex algorithm. The second method is based on the max-flow min-cut theorem states that the maximum flow through any network from a given source to a given sink is exactly equal to the minimum sum of a cut.
To solve this problem, there are limited softwares that have their own complexities to work with. Optimizatin City group has designed and implemented the online solver of the maximum flow problem. In the following, we review how to use the online solver.
The GUI of the online solver of the maximum flow problem is as follows.
Problem input
To find the optimal solution of the maximum flow problem, the required inputs are as follows:
n: the number of network nodes.
m: the number of network edges. Each edge consists of two directed arcs.
source: The source node of the network.
sink: the destination node of the network.
nodei: vector has 2m+1 components that stores the beginning node of each arc. The first component is considered to be zero. We put a zero number for the components that do not have an arc.
nodej: vector has 2m+1 components that stores the end node of each arc. The first component is considered to be zero. We put a zero number for the components that do not have an arc.
capacity: The vector has 2m+1 components that stores the capacity of each arc. The first component is considered to be zero. We put a zero number for the components that do not have an arc.
Note: The network must be non-cyclic, that is, there should be no cycle in the network.
Example: To teach how to use this solver, we use the following example. Consider the network with the following capacity. The numbers on the edges are the capacity of each edge. What is the maximum current passing from node 5 to node 2?
Solution:The input information for the given network is as follows.
Entering information in the online solver of the maximum flow problem is as follows. Note that each entry should be separated by a comma.
After entering the data, we click on the RUN button.
The result of running the algorithm is as follows.
In the output, the phrase “Nodes in the minimum cut set” means that nodes 1 and 5 are in the minimum cut set, as shown in the figure below with the red line.
The term “Amount of flow through each node” indicates the flow through each node in the answer with the maximum flow from node 5 to node 2.
The term “Amount of flow through each edge” indicates the flow through each edge in the answer with the maximum flow from node 5 to node 2.
In this example, the maximum flow from node 5 to node 2 is equal to 60.