Minimum-cost flow problem on arvau

Wikipedia / Minimum-cost flow problem

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.

Definition

A flow network is a directed graph.

The definition of the problem is to minimize the total cost of the flow over all edges:

with the constraints

|- | Capacity constraints |- | Skew symmetry |- | Flow conservation |- | Required flow |}

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 matchingss.

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.

A related problem is the minimum cost circulation problem.

The following problems are special cases of the minimum cost flow problem (we provide brief sketches of each applicable reduction, in turn):

Shortest path problem. Give all edges infinite capacity.
Maximum flow problem.
Assignment problem. 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. Some of them are generalizations of maximum flow algorithms, others use entirely different approaches.

Well-known fundamental algorithms (they have many variations):

Cycle canceling: a general primal method.
Cut canceling: a general dual method.
Minimum mean cycle canceling: a simple strongly polynomial algorithm.
Successive shortest path and capacity scaling: dual methods, which can be viewed as the generalization of the Ford–Fulkerson algorithm.
Cost scaling: a primal-dual approach, which can be viewed as the generalization of the push-relabel algorithm.
Network simplex algorithm: a specialized version of the linear programming simplex method.
Out-of-kilter algorithm by D. R. Fulkerson

Cycle canceling algorithms

These algorithms are iterative and like the Ford–Fulkerson algorithm. The algorithms then start with an arbitrary feasible flow and iteratively improve the cost of the solution by pushing flow around negative-cost cycles. In the Minimum mean cycle canceling, the algorithm selects a cycle that has minimum mean cost (the ratio of the total cycle cost to the number of arcs). Such a cycle can be found in polynomial time (by binary search using the Bellman-Ford algorithm) and the total number of iterations has been proven to be polynomial.

Almost-linear time algorithm

A deterministic almost-linear time algorithm is known to solve the minimum-cost flow problem on directed graphs..

Application

Minimum weight bipartite matching

Given a bipartite graph , 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 whose total weight is minimized. The idea is to reduce this problem to a network flow problem.

Let . 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 G if and only if there a minimum cost flow in G.