Network flow problem

Last updated November 17, 2024

In combinatorial optimization, network flow problems are a class of computational problems in which the input is a flow network (a graph with numerical capacities on its edges), and the goal is to construct a flow, numerical values on each edge that respect the capacity constraints and that have incoming flow equal to outgoing flow at all vertices except for certain designated terminals.^[1]

Specific types of network flow problems include:

The maximum flow problem, in which the goal is to maximize the total amount of flow out of the source terminals and into the sink terminals^[1]^{: 166–206}
The minimum-cost flow problem, in which the edges have costs as well as capacities and the goal is to achieve a given amount of flow (or a maximum flow) that has the minimum possible cost^[1]^{: 294–356}
The multi-commodity flow problem, in which one must construct multiple flows for different commodities whose total flow amounts together respect the capacities^[1]^{: 649–694}
Nowhere-zero flow, a type of flow studied in combinatorics in which the flow amounts are restricted to a finite set of nonzero values

The max-flow min-cut theorem equates the value of a maximum flow to the value of a minimum cut, a partition of the vertices of the flow network that minimizes the total capacity of edges crossing from one side of the partition to the other. Approximate max-flow min-cut theorems provide an extension of this result to multi-commodity flow problems. The Gomory–Hu tree of an undirected flow network provides a concise representation of all minimum cuts between different pairs of terminal vertices.

Algorithms for constructing flows include

Dinic's algorithm, a strongly polynomial algorithm for maximum flow^[1]^{: 221–223}
The Edmonds–Karp algorithm, a faster strongly polynomial algorithm for maximum flow
The Ford–Fulkerson algorithm, a greedy algorithm for maximum flow that is not in general strongly polynomial
The network simplex algorithm, a method based on linear programming but specialized for network flow^[1]^{: 402–460}
The out-of-kilter algorithm for minimum-cost flow^[1]^{: 326–331}
The push–relabel maximum flow algorithm, one of the most efficient known techniques for maximum flow

Otherwise the problem can be formulated as a more conventional linear program or similar and solved using a general purpose optimization solver.

Related Research Articles

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink.

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

In graph theory, a minimum cut or min-cut of a graph is a cut that is minimal in some metric.

In graph theory, a connected graph is $k$ -edge-connected if it remains connected whenever fewer than $k$ edges are removed.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the network simplex algorithm.

The circulation problem and its variants are a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink. In variants of the problem, there are multiple commodities flowing through the network, and a cost on the flow.

In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see Buluc et al. (2013). Two common examples of graph partitioning are minimum cut and maximum cut problems.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets $S$ and $T$ , such that the number of edges between $S$ and $T$ is as large as possible. Finding such a cut is known as the max-cut problem.

In graph theory and combinatorial optimization, a closure of a directed graph is a set of vertices C, such that no edges leave C. The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem. It may be used to model various application problems of choosing an optimal subset of tasks to perform, with dependencies between pairs of tasks, one example being in open pit mining.

In mathematics, the minimum $k$ -cut is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least $k$ connected components. These edges are referred to as $k$ -cut. The goal is to find the minimum-weight $k$ -cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.

Approximate max-flow min-cut theorems are mathematical propositions in network flow theory. Approximate max-flow min-cut theorems deal with the relationship between maximum flow rate ("max-flow") and minimum cut ("min-cut") in a multi-commodity flow problem. The theorems have enabled the development of approximation algorithms for use in graph partition and related problems.

In graph theory, the cutwidth of an undirected graph is the smallest integer $with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered, then for every, the number of edges with and is at most .$

In the theory of combinatorial optimization, submodular flow is a general class of optimization problems that includes as special cases the minimum-cost flow problem, matroid intersection, and the problem of computing a minimum-weight dijoin in a weighted directed graph. It was originally formulated by Jack Edmonds and Rick Giles, and can be solved in polynomial time.

References

1 2 3 4 5 6 7 Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.

This set index article includes a list of related items that share the same name (or similar names).
If an internal link incorrectly led you here, you may wish to change the link to point directly to the intended article.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[FNbook-1] 1 2 3 4 5 6 7 Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.

[1]