The problem was formalized by the French mathematician Gaspard Monge in 1781.
In 1930, in the collection Transportation Planning Volume I for the National Commissariat of Transportation of the Soviet Union, he published a paper "Methods of Finding the Minimal Kilometrage in Cargo-transportation in space".
[2][3] Major advances were made in the field during World War II by the Soviet mathematician and economist Leonid Kantorovich.
Suppose for the sake of argument that these mines and factories form two disjoint subsets
Having made the above assumptions, a transport plan is a bijection
More specifically, it is equivalent to finding a minimum weight matching in a bipartite graph.
The following simple example illustrates the importance of the cost function in determining the optimal transport plan.
books of equal width on a shelf (the real line), arranged in a single contiguous block.
Two obvious candidates for the optimal transport plan present themselves: If the cost function is proportional to Euclidean distance (
If, on the other hand, we choose the strictly convex cost function proportional to the square of Euclidean distance (
If the latter is considered instead, then, of the two transport plans, the second is always optimal for the Euclidean distance, while, provided there are at least 3 books, the first transport plan is optimal for the squared Euclidean distance.
The following transportation problem formulation is credited to F. L. Hitchcock:[7] Tjalling Koopmans is also credited with formulations of transport economics and allocation of resources.
The transportation problem as it is stated in modern or more technical literature looks somewhat different because of the development of Riemannian geometry and measure theory.
The mines-factories example, simple as it is, is a useful reference point when thinking of the abstract case.
Monge's formulation of the optimal transportation problem can be ill-posed, because sometimes there is no
We can improve on this by adopting Kantorovich's formulation of the optimal transportation problem, which is to find a probability measure
It can be shown[10] that a minimizer for this problem always exists when the cost function
is a tight collection of measures (which is guaranteed for Radon spaces
A gradient descent formulation for the solution of the Monge–Kantorovich problem was given by Sigurd Angenent, Steven Haker, and Allen Tannenbaum.
[11] The minimum of the Kantorovich problem is equal to where the supremum runs over all pairs of bounded and continuous functions
, the Monge–Kantorovich problem rewrites: which has dual: where the infimum runs over bounded and continuous function
The objective function in the primal Kantorovich problem is then and the constraint
expresses as and In order to input this in a linear programming problem, we need to vectorize the matrix
, the linear programming formulation of the problem is which can be readily inputted in a large-scale linear programming solver (see chapter 3.4 of Galichon (2016)[12]).
, and: for the dual, which can be rewritten as: which is a finite-dimensional convex optimization problem that can be solved by standard techniques, such as gradient descent.
Consider a variant of the discrete problem above, where we have added an entropic regularization term to the objective function of the primal problem One can show that the dual regularized problem is where, compared with the unregularized version, the "hard" constraint in the former dual (
) has been replaced by a "soft" penalization of that constraint (the sum of the
The optimality conditions in the dual problem can be expressed as Denoting
, solving the dual is therefore equivalent to looking for two diagonal positive matrices
The Monge–Kantorovich optimal transport has found applications in wide range in different fields.