Minimum-cost flow problem

Lore & Background

The minimum-cost flow problem is defined on a directed graph G = (V, E) with a source vertex s and a sink vertex t. Each edge (u, v) has capacity c(u, v) > 0, flow f(u, v), and cost a(u, v). The cost of sending flow along an edge is f(u, v) · a(u, v). The problem requires an amount of flow d to be sent from source s to sink t, minimizing the total cost over all edges. Most minimum-cost flow algorithms support edges with negative costs. A variation of this problem is to find a flow which is maximum but has the lowest cost among the maximum flow solutions, called a minimum-cost maximum-flow problem. The related minimum cost circulation problem has no source and sink, instead having costs and lower and upper bounds on each edge. Any minimum-cost flow instance can be converted into a minimum cost circulation instance by adding an extra edge from sink t to source s with capacity and lower bound both equal to d. Several well-known problems are special cases of the minimum cost flow problem, including the shortest path problem, the maximum flow problem, and the assignment problem. The problem can be solved by linear programming, and many combinatorial algorithms exist, such as cycle canceling, cut canceling, minimum mean cycle canceling, successive shortest path, capacity scaling, cost scaling, network simplex algorithm, and the out-of-kilter algorithm by D. R. Fulkerson.

Reader's Guide

The minimum-cost flow problem holds a central place in network flow theory because it generalizes many other fundamental problems, including the shortest path problem, maximum flow problem, and assignment problem. Its ability to model real-world scenarios such as delivery route optimization with capacity and cost constraints makes it practically important. The problem can be solved efficiently using the network simplex algorithm, a specialized version of the linear programming simplex method. A deterministic almost-linear time algorithm is known to solve the problem on directed graphs with m edges and polynomially bounded demands, costs, and capacities, running in time m^{1+o(1)}. The cycle canceling algorithms, which iteratively improve flow by pushing flow around negative-cost cycles, include the minimum mean cycle canceling method that can find such cycles in polynomial time using binary search with the Bellman-Ford algorithm. The problem's versatility and efficient solvability have made it a cornerstone of operations research and computer science.

Did You Know?

• The minimum cost flow problem can be solved by linear programming since it optimizes a linear function with all linear constraints.
• Any minimum-cost flow instance can be converted into a minimum cost circulation instance by adding an edge from sink to source with capacity and lower bound both equal to the required flow amount d.
• The out-of-kilter algorithm for this problem was developed by D. R. Fulkerson.
• A deterministic almost-linear time algorithm exists for the problem on directed graphs, running in time m^{1+o(1)}.