The minimum-cost flow problem 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.
Definition
A flow network is a directed graph with a source vertex and a sink vertex, where each edge has capacity, flow and cost, with most minimum-cost flow algorithms supporting edges with negative costs. The cost of sending this flow along an edge is. The problem requires an amount of flow to be sent from source to sink. The definition of the problem is to minimize the total cost of the flow over all edges: with the constraints
Relation to other problems
A variation of this problem is to find a flow which is maximum, but has the lowest cost among the maximum flow solutions. This could be called a minimum-cost maximum-flow problem and is useful for finding minimum cost maximum matchings. With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, one can find the maximum flow by performing a binary search on. A related problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. This is achieved by setting the lower bound on all edges to zero, and then making an extra edge from the sink to the source, with capacity and lower bound, forcing the total flow from to to also be. The following problems are special cases of the minimum cost flow problem :
Shortest path problem. Require that a feasible solution to the minimum cost flow problem sends one unit of flow from a designated source to a designated sink. Give all edges infinite capacity.
Maximum flow problem. Let all nodes have zero demand, and let the cost associated with traversing any edge be zero. Now, introduce a new edge from the current sink to the current source. Stipulate that the per-unit cost of sending flow across edge equals, and permit infinite capacity..
Assignment problem. Suppose that each partite set in the bipartition has vertices, and denote the bipartition by. Give each supply and give each demand. Each edge is to have unit capacity.
Solutions
The minimum cost flow problem can be solved by linear programming, since we optimize a linear function, and all constraints are linear. Apart from that, many combinatorial algorithms exist, for a comprehensive survey, see. Some of them are generalizations of maximum flow algorithms, others use entirely different approaches. Well-known fundamental algorithms :
Given a bipartite graphG =, the goal is to find the maximum cardinality matching in G that has minimum cost. Let w: E → R be a weight function on the edges of E. The minimum weight bipartite matching problem or assignment problem is to find a perfect matching M ⊆ E whose total weight is minimized. The idea is to reduce this problem to a network flow problem. Let G′ =. Assign the capacity of all the edges in E′ to 1. Add a source vertex s and connect it to all the vertices in A′ and add a sink vertex t and connect all vertices inside group B′ to this vertex. The capacity of all the new edges is 1 and their costs is 0. It is proved that there is minimum weight perfect bipartite matching in Gif and only if there a minimum cost flow in G′.
